РАВНОСИЛЬНОСТЬ ФОРМУЛ АЛГЕБРЫ ВЫСКАЗЫВАНИЙ

Равносильность формул алгебры высказываний. Свойства отношения равносильности: рефлексивность, симметричность, транзитивность. Основные равносильности, определяющие свойства логических операций над формулами (законы алгебры высказываний).

Правила равносильных преобразований формул алгебры высказываний (правилo подстановки). Методы доказательства равносильности формул: посредством равносильных преобразований и с помощью таблицы истинности. Совместность множества формул. Упрощение систем высказываний.

10.1. Доказать, что на множестве формул алгебры высказываний отношение равносильности формул является отношением эквивалентности.

10.2. Доказать законы алгебры высказываний:

1)                                                                закон тождества;

2)                                                      закон двойного отрицания;

3)  и                                   законы идемпотентности;

4) ,  и , ;

5)                                     закон исключенного третьего;

6)                                               закон противоречия;

7)  и                        законы коммутативности;

8)  и        законы ассоциативности;

9)                                                          законы

и                                  дистрибутивности;

10)                                  закон замены импликации;

11)               закон удаления эквиваленции;

12)  и                      законы де Моргана;

13)  и                                законы поглощения;

14)  и               законы склеивания;

15)                                 закон контрапозиции;

16)                        закон силлогизма;

17)                                    закон заключения.

10.3. Докажите равносильность следующих формул двумя способами: посредством равносильных преобразований и с помощью таблиц истинности:

1)  и ;

2)  и ;

3)  и ;

4)  и ;

5)  и ;

6)  и ;

7)  и ;

8)  и ;

9)  и .

10.4.   Доказать, что существует  неэквивалентных формул от  переменных.

10.5.   Пусть формулы  и  эквивалентны и  является подформулой формулы . Доказать, что если формула  получена из формулы  подстановкой вместо подформулы  формулы , то  и эквивалентны.

10.6.   Упростить следующие формулы посредством равносильных преобразований:

1) ;

2) ;

3) ;

4) ;

5) ;

6) ;

7) ;

8) ;

9) .

10.7.   Определить, на каких наборах значений переменных следующие формулы ложны:

1) ;

2) ;

3) ;

4) ;

5) .

10.8.   Доказать, что если формулы  и  тождественно истинны, то формула  тождественно истинна.

10.9.   Доказать, что если формулы  и тождественно истинны, то формула  тождественно ложна.

10.10.   Доказать, что если формулы  и  тождественно истинны, то формула  тождественно истинна.

10.11.   Доказать, что если формулы ,  и  тождественно истинны, то формула  тождественно ложна.

10.12.   Доказать, что если ,  тождественно истинны, то формула  тождественно истинна.

10.13.   Пусть буквы , ,  обозначают суждения:

 – «Множество рациональных чисел счетно»,

 – «Множество рациональных чисел конечно»,

 – «Множество комплексных чисел счетно».

Переведите на обычный язык следующие формулы: , , , . Определите их истинность.

10.14.   Формализовать утверждения и привести их по возможности к более простому виду:

1) Если функция непрерывна в данной точке, то она не имеет в ней разрыва; функция имеет разрыв в данной точке.

2) Либо Санчо Панса станет губернатором, либо Дон Кихот – не доблестный рыцарь, а Дон Кихот – доблестный рыцарь, так как Дульцинея Тобосская любит только доблестных рыцарей.

3) Если треугольник равносторонний, то все углы в треугольнике равны или все его высоты имеют одинаковую длину; и неверно, что треугольник равносторонний, но высоты треугольника не равны.

4) Необходимым условием победы спортсмена является его хорошая физическая форма.

5) Хорошей физической формы спортсмена не достаточно для его победы.

6) Чтобы быть допущенным к экзамену необходимо и достаточно сдать зачет.

7) Чтобы сдать экзамен, необходимо, но не достаточно сдать зачет.

8) Чтобы улучшить состояние здоровья достаточно, но не необходимо съездить на море.

9) Отрезки , ,  являются сторонами треугольника, если , но для того чтобы отрезки , ,  не являлись сторонами треугольника, необходимо, чтобы .

10) Чтобы Боб был счастлив, достаточно, чтобы ему купили велосипед или отпустили в кино; чтобы Боб был счастлив и его отпустили в кино, необходимо, чтобы ему купили велосипед; Боб счастлив, так как ему купят велосипед и отпустят в кино.

10.15.   До царя Гороха дошла молва, что кто-то из троих богатырей убил Змея Горыныча. Царь приказал всем троим явиться ко двору и молвили они:

Илья Муромец:   «Змея убил Добрыня Никитич»;

Добрыня Никитич:  «Змея убил Алеша Попович»;

Алеша Попович:   «Я убил Змея».

При этом известно, что один из них сказал правду, а двое слукавили. Кто убил змея?

10.16.   В велогонках приняли участие пять школьников. После гонок пять болельщиков заявили:

«Коля занял первое место, а Ваня – четвертое»;

«Сережа занял второе место, а Ваня – четвертое»;

«Сережа занял второе место, а Коля – третье»;

«Толя занял первое место, а Надя – второе»;

«Надя заняла третье место, а Толя – пятое».

Зная, что одно из показаний каждого болельщика верное, а другое - неверное, найти правильное распределение мест.

10.17.   В стране Чудес проводилось следствие по делу об украденной муке. На суде Мартовский Заяц заявил, что муку украл Болванщик. В свою очередь Болванщик и Соня дали показания, которые по каким-то причинам не были записаны. В ходе судебного заседания выяснилось, что муку украл лишь один из трех подсудимых и что только он дал правдивые показания. Кто украл муку?