Математика \ Математическая логика и теория алгоритмов

Математическая логика и теория алгоритмов: Методические указания к практическим занятиям, страница 6

в)

Ответ:

4). Составьте схему цепи с тремя независимыми контактами, которая замкнута тогда и только тогда, когда:

а) замкнута по меньшей мере два контакта;

б) замкнуты не более, чем два контакта;

в) разомкнут только один контакт.

Занятие 4. Логические функции (предикаты) и операции над ними

В традиционной логике в элементарном высказывании различаются субъект (то, что утверждается о субъекте), иначе говоря, подлежащее (субъект) и сказуемое (предикат). Предикат означает в этом случае свойство предмета.

В математической логике понятие предиката берется в более широком смысле как отношение между предметами, то есть предикат трактуется как логическая функция одной или нескольких предметных переменных.

Определение 8 [3]. местным предикатом, определенным на множествах называется предложение, содержащее переменных превращающееся в высказывание при подстановке вместо этих переменных любых конкретных элементов из множеств собственно. Это высказывание может быть либо истинным (предикат принимает значение 1), либо ложным (предикат принимает значение 0). Если есть область определения предиката то есть подмножество , на котором он обращается в истинное высказывание, называется множеством истинности, то есть

Если то предикат называется тождественно истинным ( опровержимым).

Если то предикат называется тождественно ложным (выполнимым).

Два предиката и называются равносильными, если Предикат называется следствием предиката , если Обозначается: и где знак равносильности, логическое следствие.

Над предикатами можно осуществлять те же логические операции, что и над высказываниями: отрицание, конъюнкцию, дизъюкнцию, импликацию, эквиваленцию и другие (известные нам) операции. При этом имеем

(1)

(2)

, (3)

где общая область определении предикатов и (формулы (1) –(2)) или область определения предиката (в формуле (3));

(4)

(5)

Логические операции преобразуют предикаты в предикаты. Рассмотрим теперь две операции, преобразующие предикаты в высказывания:

1) подстановка вместо всех предметных переменных их значений:

2) связывание всех переменных кванторами общности или существования;

3) подстановки вместо переменных, не связанных кванторами (то есть вместо свободных переменных), их значений – это комбинация первых двух операций.

Связанные переменные – это те переменные, которые фигурируют и в предикате, и в кванторной записи типа и т.п., где для всякого квантор всеобщности (общности), а существует квантор существования.