Основные законы дизъюнкции, конъюнкции и отрицания

1. Идемпотентности дизъюнкции P P = P.

Идемпотентности конъюнкции P&P = P

2. Коммутативности дизъюнкции P Q = Q P.

Коммутативности конъюнкции P&Q = Q&P.

3. Ассоциативности дизъюнкции P (Q Т) = (P Q) Т.

Ассоциативности конъюнкции P& (Q&Т) = (P&Q)&Т.

4. Дистрибутивности конъюнкции относительно дизъюнкции

P& (Q Т) = (P&Q) (P&Т).

Дистрибутивности дизъюнкции относительно конъюнкции

P (Q&Т) = (P Q)&(P Т).

Скобки в выражениях P&Q Т = P&Q P&Т не ставятся так как конъюнкция & как мультипликативная операция более старшая по отношению к дизъюнкции, являющейся аддитивной операцией, поэтому выполняется в первую очередь.

5. Двойного отрицания нене P = P

6. де-Моргана неP неQ = не(P&Q) неP&неQ = не(P Q).

7. Склеивания P&Q P&неQ = P; (P Q)&(P неQ) = P.

8. Поглощения Р P&Q = P; P&(P Q) = P.

9. Законы, определяющие действия с константами 0 и 1:

Р 0 = Р, Р&0 = 0, Р 1 = 1,

Р&1 = Р, Р неР = 1, Р&неР = 0.

Если в сложном выражении скобок нет, то операции надо выполнять в следующем порядке: конъюнкция, дизъюнкция, импликация, эквивалентность, отрицание.

Помимо этих связок используются еще три связки полученные из вышеуказанных связок

Название	Прочтение	Обозначение
Штрих Шеффера	Антиконъюнкция
Стрелка Пирса	Антидизъюнкция
Сумма по модулю два	Антиэквивалентность

Штрих Шеффера или антиконъюнкция, по определению

Стрелка Пирса или антидизъюнкция, по определению

Сумма по модулю два или антиэквивалентность, по определению

Таблицы истинности этих операций

X	Y	Штрих Шеффера	Стрелка Пирса	Сумма по модулю 2

Соглашения относительно расстановки скобок.

1. Внешние скобки не пишутся.

Пример. Вместо пишут

2. На множестве вводятся транзитивное отношение < «быть более сильным» и отношение эквивалентности ~ «быть равносильным» по правилам показанным на рис.

~ ~

~

Согласно этим отношениям недостающие скобки в формуле расставляются последовательно, начиная с наиболее сильных связок и кончая наиболее слабыми, а для равносильных связок расстановка скобок выполняется слева направо.

Дата добавления: 2015-06-27