4.Импликация. Импликацией двух высказываний P и Q называется высказывание, истинное тогда и только тогда, когда высказывание P истинно, а Q - ложно.
Обозначается P Q (или P Q ). Высказывание P называется посылкой импликации, а высказывание Q - следствием.
H |
Q |
PР |
P |
Q |
Q |
|
|
|
И |
И |
И |
И |
И |
И |
|
|
|
И |
Л |
ЛЛ |
И |
Л |
|
|
|
|
Л |
И |
И |
Л |
И |
И |
|
|
|
Л |
Л |
И |
Л |
Л |
И |
|
|
|
5.Эквиваленция. Эквиваленцией двух высказываний P и Q называется высказывание, истинное тогда и только тогда, когда истинности высказываний совпадают.
Обозначается P Q или P Q .
Р |
Q |
Р |
P |
Q |
P Q |
|
|
|
И |
И |
И |
И |
И |
И |
И |
Л |
Л |
И |
Л |
Л |
|
|
|
Л |
И |
Л |
Л |
И |
Л |
Л |
Л |
И |
Л |
Л |
И |
|
|
|
С помощью этих основных таблиц истинности можно составлять таблицы истинности сложных формул.
Булевы функции
Определение. Булевой функцией f (X1, X2 ,…, Xn ) называется произвольная n - местная функция, аргументы и значения которой принадлежат множеству {0,1} .
Вообще говоря между логическими высказываниями, логическими связками и булевыми функциями просматривается явная аналогия. Если логические функции могут принимать значения истинно или ложно, то для булевой функции аналогами этих значений будут значения
0 или 1.
Для булевых функций также можно составить таблицы значений, соответствующим основным логическим операциям.
X1 |
X2 |
←X1 |
X1&X2 |
X1 X2 |
X1 X2 |
X1 X2 |
|
|
|
|
|
1 |
|
1 |
1 |
0 |
1 |
1 |
1 |
|
|
|
|
|
|
0 |
|
1 |
0 |
0 |
0 |
1 |
0 |
|
|
|
|
|
|
1 |
|
0 |
1 |
1 |
0 |
1 |
0 |
|
|
|
|
|
|
1 |
|
0 |
0 |
1 |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
70
Исчисление предикатов
Определение. Предикатом P(x1, x2 ,…, xn ) называется функция, переменные которой
принимают значения из некоторого множества M , а сама функция принимает два значения: И (истина) и Л (ложь), т.е.
P(x1, x2 ,…, xn ) : M n → {И, Л}
Предикат от n аргументов называется n - местным предикатом. Высказывания считаются нуль - местными предикатами.
Над предикатами можно производить обычные логические операции, в результате которых получаются новые предикаты.
Кроме обычных логических операций к предикатам применяются также специальные операции, называемые кванторами.
Кванторы бывают двух видов:
1.Квантор общности. Обозначается ( x)P(x) . Квантором общности называется высказывание истинное, когда P(x) истинно для каждого элемента х из множества M , и ложное - противном случае.
2.Квантор существования. Обозначается ( x)P(x) . Квантором существования называется высказывание, истинное, когда существует элемент из множества М, для которого P(x) истинно, и ложное в противном случае.
Операцию связывания квантором можно применять и к предикатам от большего числа переменных.
Для формул логики предикатов сохраняется справедливость всех правил равносильных преобразований логики высказываний. Кроме того, справедливы следующие свойства:
Перенос квантора через отрицание.
←( x)A(x) ≡ ( x)←A(x) ; ←( x)A(x) ≡ ( x)←A(x) ;
Вынесение квантора за скобки.
( x)(A(x)&B) ≡ ( x)A(x)&B ; ( x)(A(x)&B) ≡ ( x)A(x)&B ; ( x)(A(x) B) ≡ ( x)A(x) B ; ( x)(A(x) B) ≡ ( x)A(x) B ;
3) Перестановка одноименных кванторов.
( y)( x)(A(x, y) ≡ ( x)( y)(A(x, y) ; ( y)( x)A(x, y) ≡ ( x)( y)A(x, y) ;
Переименование связанных переменных. Если заменить связанную переменную формулы A другой переменной, не входящей в эту формулу, в кванторе и всюду в области действия квантора получаем формулу, равносильную A .
Исчисление предикатов базируется на приведенных выше свойствах и правилах, называемых аксиомами.
Какими бы ни были формулы А и В для них справедливы следующие аксиомы: 1) A (B A) ;
2) (A (B C)) ((A B) (A C));
3)(←B ←(A) ((←B A) B);
4)( xi )A(xi ) A(xi ) , где формула A(xi ) не содержит переменной xi .
5)A(xi ) ( xi )A(xi ) , где формула A(xi ) не содержит переменной xi .
71