3. Законы логики высказываний

Основными законами логики высказываний называют следующие равносильные формулы.

Основные законы логики высказываний
┐(┐А)  (А)	– закон двойного отрицания.
(А B)  (B А)	– коммутативность конъюнкции.
(А B)  (B А)	– коммутативность дизъюнкции.
А (B C)  (А B) C	– ассоциативность конъюнкции.
А (B C)  (А B) C	– ассоциативность дизъюнкции.
законы Моргана
┐(А B)(┐А) (┐B)				┐(А B)(┐А) (┐B)
законы дистрибутивности
А (B C)  (А B) (А C)				А (B C)  (А B) (А C)
законы поглощения
А (А B)  А				А (А B)  А
законы идемпотентности
А АА				А АА
и другие
АB  ┐А B			АB (АB) (BА)
А ┐А  1		А 11			А 0А
А ┐А  0		А 1 А			А 00

Лекция № 3. Алгебра предикатов

1. Понятие предиката.

2. Операции над предикатами.

3. Кванторы.

4. Множество истинности предиката.

1. Понятие предиката

Определение. n-местным предикатом, определенным на множествах M₁, M₂, … M_n, называется выражение, содержащее n переменных x₁, x₂, .. x_n, превращающееся в высказывание при подстановке вместо этих переменных конкретных элементов a_iM_i i=1,2… n соответственно.

Обозначается n-местный предикат так: P(x₁, x₂, .. x_n), причем высказывание считается 0-местным предикатом.

Пример 1. Одноместными предикатами являются выражения:

1. «x – четно»;

2. sin²x+cos²x=1;

3. x²<0;

4. «Река x впадает в озеро Байкал».

В то же время, выражение:

«Для всех вещественных чисел x выполняется равенство x²+x–6=0» одноместным предикатом не является. Это 0-местный предикат или просто высказывание, причем высказывание ложное.

Пример 2. Двухместными предикатами являются выражения:

1) «x есть брат y» (x, y «пробегают» множество всех людей);

2) «прямая x перпендикулярна прямой y» (x, y «пробегают» множество всех прямых одной плоскости).

2. Операции над предикатами

Над предикатами определены те же логические операции, что и над высказываниями.

Определение. Отрицанием n-местного предиката P(x₁, x₂, .. x_n), заданного над множествами M₁, M₂, … M_n, называется новый n-местный предикат над этими множествами, обозначаемый ┐P(x₁, x₂, .. x_n). Этот предикат обращается в истинное высказывание на тех только тех значениях переменных из множеств M₁, M₂, … M_n, при которых P(x₁, x₂, .. x_n) обращается в ложное высказывание, и обращается в ложное при тех значениях переменных, при которых P(x₁, x₂, .. x_n) обращается в истинное высказывание.

Определение. Дизъюнкцией n-местного предиката P(x₁, x₂, .. x_n) и n-местного предиката Q(x₁, x₂, .. x_n), заданных над множествами M₁, M₂, … M_n, называется новый n-местный предикат над этими множествами, обозначаемый P(x₁, x₂, .. x_n) Q(x₁, x₂, .. x_n). Этот предикат обращается в ложное высказывание на тех только тех значениях переменных из множеств M₁, M₂, … M_n, при которых оба предиката P(x₁, x₂, .. x_n) и Q(x₁, x₂, .. x_n) обращаются в ложное высказывание.

Определение. Конъюнкцией n-местного предиката P(x₁, x₂, .. x_n) и n-местного предиката Q(x₁, x₂, .. x_n), заданных над множествами M₁, M₂, … M_n, называется новый n-местный предикат над этими множествами, обозначаемый P(x₁, x₂, .. x_n) Q(x₁, x₂, .. x_n). Этот предикат обращается в истинное высказывание на тех только тех значениях переменных из множеств M₁, M₂, … M_n, при которых оба предиката P(x₁, x₂, .. x_n) и Q(x₁, x₂, .. x_n) обращаются в истинное высказывание.

Определение. Импликацией n-местного предиката P(x₁, x₂, .. x_n) и n-местного предиката Q(x₁, x₂, .. x_n), заданных над множествами M₁, M₂, … M_n, называется новый n-местный предикат над этими множествами, обозначаемый P(x₁, x₂, .. x_n)  Q(x₁, x₂, .. x_n). Этот предикат обращается в ложное высказывание на тех только тех значениях переменных из множеств M₁, M₂, … M_n, при которых предикат P(x₁, x₂, .. x_n) обращается в истинное высказывание, а предикат Q(x₁, x₂, .. x_n) в ложное.

Определение. Эквивалентностью n-местного предиката P(x₁, x₂, .. x_n) и n-местного предиката Q(x₁, x₂, .. x_n), заданных над множествами M₁, M₂, … M_n, называется новый n-местный предикат над этими множествами, обозначаемый P(x₁, x₂, .. x_n)Q(x₁, x₂, .. x_n). Этот предикат обращается в истинное высказывание на тех только тех значениях переменных из множеств M₁, M₂, … M_n, при которых предикаты P(x₁, x₂, .. x_n) и Q(x₁, x₂, .. x_n) обращаются либо в истинное, либо в ложное высказывание одновременно.