Синтаксис, семантика и правила вывода в исчислении высказываний

Синтаксис исчисления высказываний определяется правилами грамматики:

Предложение: = Элементарное предложение / Сложное предложение

Сложное предложение: = Предложение Связка Предложение / ^Предложение / (Предложение)

Связка: = Ù / Ú / ^ / ® /»

Семантика исчисления высказываний определяется с помощью таблиц истинности.

К правилам вывода относятся:

1.

Если посылка А есть истина, то и заключение В есть истина.

2.Исключение И:

 

 

Знание того, что А и В есть истина, должно означать, что А есть истина и В есть истина.

3.Интродукция ИЛИ:

 

 

Если А есть истина, то А или В есть истина. То же самое имеет место, если В есть истина.

4.Интродукция И:

 

 

Если А есть истина и В есть истина, то А И В есть истина.

5.Двойное отрицание:

Если А есть не не истина, то А есть истина.

6.Единичная резолюция:

 

 

Если А или В есть истина и не В, то А есть истина. Точно также, если не А, то В – истина.

7.Резолюция:

 

Если А или В и не В или С, то, поскольку В не может быть истинно и ложно одновременно, должно быть А или С истинно.

Пример: Имеется следующая информация.

Если аккумулятор машины разряжен, то машина не заводится. Если машина Ивана не заводится и текущее время оказывается позже восьми часов утра, то Иван опоздает на поезд. Однажды после восьми утра аккумулятор Ивана оказался разряженным.

Используя логические правила вывода, доказать, что Иван опоздает на поезд.

В символьных обозначениях информация может быть представлена в следующем виде:

P: аккумулятор разряжен.

Q: машина не заводится.

R: время после восьми утра.

S: Иван опоздал на поезд.

Правило 1: P ® Q.

Правило 2. QÙR ® S.

Известно, что P и R есть истина. Задачей является доказать S. Доказательство строится следующим образом:

1. P – дано.

2. R – дано.

3. Q следует из 1 и правила 1 по правилу modes ponens.

4. QÙR следует из 3 и 2 по правилу интродукции И.

5. S следует из 4 и правила 2 по правилу modes ponens.

Исчисление предикатов предполагает, что мир можно моделировать с помощью фактов. Но для реальных приложений исчисления высказываний недостаточно.

Практические задания

Задание 1

Даны логические функции:

 

 

Получить значения этих функций с помощью таблиц истинности. Преобразовать к алгебраическому виду и определить значения для x =1, y =1, z = 0. Преобразовать к виду с использованием только операций дизъюнкции, конъюнкции и отрицания. Упростить. Привести к СДНФ и СКНФ. Восстановить СДНФ и СКНФ по таблице истинности. Построить импликантную таблицу и определить сокращенную ДНФ с использованием метода Петрика. Минимизировать с использованием алгоритма Квайна и диаграммы Вейча.

 

Задание 2

Если собака видит кошку, то она за ней гонится. Если за котом Васькой гонится собака и рядом есть дерево, то кот Васька забирается на дерево. В саду много деревьев. Однажды, в саду Ваську увидела собака.

Доказать, пользуясь логическими правилами вывода, что Васька забрался на дерево.

Компьютерное задание

Реализовать программу решающую следующую задачу:

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

На выходе программы – СДНФ, СКНФ, диаграмма Вейча и минимальная нормальная форма.