logo
Predmet

[Править]Логика высказываний

1. Язык логики высказываний. Логические связки и таблицы истинности. Приведение формул к дизъюнктивной и конъюнктивной нормальным формам. Булевы функции. Полные системы булевых функций. Теорема Поста. Полиномы Жегалкина.

2. Гильбертовский вариант исчисления для логики высказываний. Алфавит, формулы, схемы аксиом и правила вывода исчисления высказываний. Вывод, выводимая формула. Семантическая корректность исчисления высказываний.

Вывод из гипотез. Теорема о дедукции для исчисления высказываний. Теорема о семантической полноте исчисления высказываний.

3. Генценовский вариант исчисления для логики высказываний. Понятие секвенциального вывода. Эквивалентность гильбертовского и генценовского вариантов исчисления высказываний. Теорема об устранении сечения. Алгоритм поиска вывода в исчислении высказываний.