Логические законы

Два высказывания являются равносильными (), если на одинаковых наборах данных они принимают одинаковые значения, т.е. для доказательства логических законов необходимо установить какие значения принимают обе части высказывания на всевозможных значениях переменных, входящих в высказывание. Такой подход возможен благодаря небольшому количеству исходных данных.

1. коммутативные (перестановочные) законы

.

Пример. “А и В сидели на трубе” равносильно “В и А сидели на трубе”.

2. ассоциативные (сочетательные) законы

Пример. “Мы с подружкой Юлей дружим с Сашей” равносильно “Я дружу с Юлей и Сашей”.

3. дистрибутивные (распределительные) законы

Пример. “Я дружу с Алексеем или Васей и Петей” эквивалентно “Я дружу с Алексеем или Васей и дружу с Алексеем или Петей”.

4. закон двойного отрицания

Пример. “Неверно, что умный в гору пойдет” эквивалентно “Умный в гору не пойдет”. “Неверно, что курица не птица” эквивалентно “Курица - птица”.

5. законы де Моргана

;

Пример. Отрицание фразы “Наша служба опасна и трудна” может иметь две формы:

а). неверно, что наша служба и опасна и трудна (левая часть закона).

б). наша служба или не опасна или не трудна (правая часть закона).

Для фразы “Была прочна палатка или был не страшен путь” есть два варианта отрицания:

а) неверно, что была прочна палатка или был не страшен путь (левая часть закона);

б) была не прочна палатка и был страшен путь (правая часть закона).

6. законы идемпотентности

7. закон исключающего третьего

Пример. У меня есть компьютер или у меня нет компьютера, третьего не дано.

8. закон непротиворечивости

Одновременно не могут быть истинными высказывание и его отрицание.

Пример. Я не Рафаэль и я - Рафаэль, т.е. одновременно нельзя быть и не быть Рафаэлем.

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

10. законы поглощения

11. закон склеивания

Пример. Фрекен Бок рассуждала следующим образом: “У меня жужжит в правом ухе и в левом или у меня жужжит в правом ухе, но не жужжит в левом”. Используя данный закон, можно было бы сказать, что у фрекен Бок жужжало только в правом ухе.

Рассмотрим доказательство закона дистрибутивности конъюнкции относительно дизъюнкции: A  (B  C)  (A  B)  (A  C).

A	B	C	B  C	A  (B C)	A  B	A  C	(AB) (AC)
1	2	3	4	5	6	7	8
0	0	0	0	0	0	0	0
0	0	1	1	0	0	0	0
0	1	0	1	0	0	0	0
0	1	1	1	0	0	0	0
1	0	0	0	0	0	0	0
1	0	1	1	1	0	1	1
1	1	0	0	1	1	0	1
1	1	1	1	1	1	1	1

Столбики 5 и 8 полностью совпали, следовательно, закон доказали.

Упражнения.

1. Докажите тождества:

1).

2).

2. Докажите ассоциативные законы и законы де Моргана.

3. Сформулируйте на русском языке отрицание фраз:

• летом мы пойдем в лес и не встретим волка;

• или кошка поймает мышку, или мышка обманет кошку;

• он ел одну лишь травку и с мухами дружил;

• это мы не проходили и это нам не задавали;

• это мы не проходили или это нам не задавали;

• скатертью дальний путь стелется и упирается прямо в небосклон;

• никогда не разрешайте ставить градусник себе, и таблеток не глотайте, и не ешьте порошков.

4. Определите значение истинности следующих высказываний:

• если 2 х 2 = 5, то лучший друг Чебурашки - крокодил Гена;

• если 2 х 2 = 5, то лучший друг Чебурашки - старуха Шапокляк;

• Шерлок Холмс и доктор Ватсон - знаменитые сыщики тогда и только тогда, когда лиса Алиса и кот Базилио - знаменитые плутишки;

• 4 - простое число или Белоснежка знакома с 7 гномами;

• Колобок ушел от волка и от лисы;

• Мойдодыр - герой сказки Пушкина, а Балда - герой сказки Чуковского;

• Мойдодыр - герой сказки Чуковского или Балда - герой сказки Чуковского;

• Мойдодыр - герой сказки Чуковского, а Балда - герой сказки Пушкина;

• Карл у Клары украл кораллы, а Клара у Карла украла кларнет или ехал Грека через реку, но не увидел в реке рака;

5. Нарисуйте на плоскости X, Y область, в которой и только в которой выполняется следующее условие: (x  y)  (x + y  0)  (y  1).