План лекции: 1. Понятие формального исчисления. 2. Понятие формулы исчисления высказываний 3. Система аксиом исчисления высказываний. 4. Правила вывода 5. Определение доказуемой формулы.

Используемая литература: 1.Игошин, В. И. Математическая логика и теория алгоритмов [Текст] : учеб. пособие для вузов / В. И. Игошин.- 3-е изд., стер. - М.: Академия, с. - (Высшее профессиональное образование). - Библиогр.: с ISBN Судоплатов, С.В. Математическая логика и теория алгоритмов [Электронный ресурс] учебник / С.В. Судоплатов, Е.В. Овчинникова. - 3-е изд. - Новосибирск : НГТУ, с. - (Учебники НГТУ). - ISBN [Электронный ресурс]. - URL: URL: 3. Балюкевич Э. Л. Математическая логика и теория алгоритмов. Учебно-практическое пособие [Электронный ресурс] / Балюкевич Э. Л., Ковалева Л. Ф. - Евразийский открытый институт, – Режим доступа: Стенюшкина, В. А. Математическая логика и теория алгоритмов [Текст] : учеб. пособие для вузов / В. А. Стенюшкина; М- во образования Рос. Федерации, Гос. образоват. учреждение высш. проф. образования "Оренбург. гос. ун-т", Каф. информатики. - Оренбург : ГОУ ОГУ, с. - Библиогр.: с. 106.

Понятие формального исчисления. Формальная система (ФС) считается заданной, если определены следующие ее компоненты: 1)алфавит; 2)совокупность правильно построенных формул; 3)множество аксиом; 4)множество правил вывода. Примеры исчислений: 1. Исчисление конечных разностей Ньютона 2. Исчисление высказываний (ИВ) 3. Исчисление предикатов (ИП) 4. Исчисление Туэ (ИТ)

Структура дисциплины «Математическая логика и теория алгоритмов

Исчисление высказываний Исчисление высказываний это аксиоматическая логическая система, интерпретацией которой является алгебра высказываний.

Алфавит ИВ Алфавит исчисления высказываний состоит из символов трех категорий: Символы первой категории: х, у, z,..., х 1, х 2,.... Эти символы называются переменными высказываниями. Символы второй категории: v, &,, _. Они носят общее название логических связок. Третью категорию составляет пара символов (, ), называемая скобками.

Понятие формулы исчисления высказываний Определение формулы исчисления высказываний. 1. Всякая переменная х, у, z,... является формулой. 2. Если А и В - формулы, то слова (А& В), (A v B), (А В), - также формулы. 3. Никакая другая строчка символов не является формулой. Переменные высказывания будем называть элементарными формулами.

Примеры формул исчисления высказываний 1. Переменные высказывания х, у, z являются формулами 2. (x & у), (x v z), (у z), ху, & x, (х & у, x v у.

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

Система аксиом исчисления высказываний Первая группа аксиом: I 1 x (y x) I 2 (x (y z)) ((x y) (x z)) Вторая группа аксиом: II 1 x & y x II 2 x & y y II 3 (z x) ((z y) (z x & y))

Система аксиом исчисления высказываний Третья группа аксиом: III 1 x x v y III 2 y x v y III 3 (x z) ((y z) (x v y z)) Четвертая группа аксиом: IV 1 IV 2 IV 3

Правила вывода 1. Правило подстановки Операция замены в формуле А переменной х формулой В носит название подстановки и символически записывается: а) Если формула А есть переменная х, то подстановка дает В. б)Если формула А есть переменная у, отличная от х, то подстановка дает А.

Правила вывода 1. Правило подстановки в)Если А - формула, для которой подстановка уже определена, то подстановка В вместо х в отрицание А есть отрицание подстановки, т.е. подстановка дает г) Если А 1 и А 2 - формулы, для которых подстановки уже определены, то подстановка дает Пример: 1. 2.

Примеры применения правила подстановки 1. Выполните подстановку 2. Укажите из какой аксиомы и с помощью какой подстановки получены следующие формулы: 2.1 из А(I 2 ), если вместо х взять формулу F, в качестве у взять FF, а в качестве z – F. 2.2 из А(I 1 ) если взять x = F и 2.3 из А(IV 1 ), если принять

Правила вывода 1. Правило подстановки Если А - доказуемая формула, то будем писать А. Тогда правило подстановки можно записать схематически следующим образом: А Читается эта запись: «Если формула А доказуема, то доказуема формула

Правила вывода 2. Правило заключения Формулировка: Если формулы А и А В доказуемы в исчислении высказываний, то формула В также доказуема. Схематическая запись этого правила имеет вид: А; А В В Сокращенно правило заключения обозначается МР (от лат. modus ponens)

Примеры применения правила заключения Пример: 1. Применить к формуле МР: Т.к. формула доказуема (из А(I 1 ), а исходная формула представляет из себя схему А(IV 2 ), то 2. Укажите недостающую формулу W так, чтобы третья из данных формул получалась из первой и второй по правилу вывода МР: 2.1 Если в схеме правила вывода МР за А принять формулу F(HF), то вторая формула данной задачи может выступить в качестве формулы АВ правила МР, где В есть формула F(G(HF)). По правилу МР она является результатом применения данного правила к этим двум формулам, т.е. является W. 2.2 Для двух формул F и G требуется сконструировать такую формулу W, чтобы из F и W по правилу МР выводилась G. Видно, что в качестве W должна быть взята формула FG. Получим

Примеры применения правила заключения Пример: 1. Применить к формуле МР: Т.к. формула доказуема (из А(I 1 ), а исходная формула представляет из себя схему А(IV 2 ), то 2. Укажите недостающую формулу W так, чтобы третья из данных формул получалась из первой и второй по правилу вывода МР: 2.1 Если в схеме правила вывода МР за А принять формулу F(HF), то вторая формула данной задачи может выступить в качестве формулы АВ правила МР, где В есть формула F(G(HF)). По правилу МР она является результатом применения данного правила к этим двум формулам, т.е. является W. 2.2 Для двух формул F и G требуется сконструировать такую формулу W, чтобы из F и W по правилу МР выводилась G. Видно, что в качестве W должна быть взята формула FG. Получим

Примеры применения правила заключения Пример: 1. Применить к формуле МР: Т.к. формула доказуема (из А(I 1 ), а исходная формула представляет из себя схему А(IV 2 ), то 2. Укажите недостающую формулу W так, чтобы третья из данных формул получалась из первой и второй по правилу вывода МР: 2.1 Если в схеме правила вывода МР за А принять формулу F(HF), то вторая формула данной задачи может выступить в качестве формулы АВ правила МР, где В есть формула F(G(HF)). По правилу МР она является результатом применения данного правила к этим двум формулам, т.е. является W. 2.2 Для двух формул F и G требуется сконструировать такую формулу W, чтобы из F и W по правилу МР выводилась G. Видно, что в качестве W должна быть взята формула FG. Получим

Примеры применения правила заключения Пример: 1. Применить к формуле МР: Т.к. формула доказуема (из А(I 1 ), а исходная формула представляет из себя схему А(IV 2 ), то 2. Укажите недостающую формулу W так, чтобы третья из данных формул получалась из первой и второй по правилу вывода МР: 2.1 Если в схеме правила вывода МР за А принять формулу F(HF), то вторая формула данной задачи может выступить в качестве формулы АВ правила МР, где В есть формула F(G(HF)). По правилу МР она является результатом применения данного правила к этим двум формулам, т.е. является W. 2.2 Для двух формул F и G требуется сконструировать такую формулу W, чтобы из F и W по правилу МР выводилась G. Видно, что в качестве W должна быть взята формула FG. Получим

Примеры применения правила заключения Пример: 1. Применить к формуле МР: Т.к. формула доказуема (из А(I 1 ), а исходная формула представляет из себя схему А(IV 2 ), то 2. Укажите недостающую формулу W так, чтобы третья из данных формул получалась из первой и второй по правилу вывода МР: 2.1 Если в схеме правила вывода МР за А принять формулу F(HF), то вторая формула данной задачи может выступить в качестве формулы АВ правила МР, где В есть формула F(G(HF)). По правилу МР она является результатом применения данного правила к этим двум формулам, т.е. является W. 2.2 Для двух формул F и G требуется сконструировать такую формулу W, чтобы из F и W по правилу МР выводилась G. Видно, что в качестве W должна быть взята формула FG. Получим

Примеры применения правила заключения Пример: 1. Применить к формуле МР: Т.к. формула доказуема (из А(I 1 ), а исходная формула представляет из себя схему А(IV 2 ), то 2. Укажите недостающую формулу W так, чтобы третья из данных формул получалась из первой и второй по правилу вывода МР: 2.1 Если в схеме правила вывода МР за А принять формулу F(HF), то вторая формула данной задачи может выступить в качестве формулы АВ правила МР, где В есть формула F(G(HF)). По правилу МР она является результатом применения данного правила к этим двум формулам, т.е. является W. 2.2 Для двух формул F и G требуется сконструировать такую формулу W, чтобы из F и W по правилу МР выводилась G. Видно, что в качестве W должна быть взята формула FG. Получим

Определение доказуемой формулы. а)Всякая аксиома является доказуемой формулой. б)Формула, полученная из доказуемой формулы путем применения подстановки вместо переменной х произвольной формулы В есть доказуемая формула. в)Формула В, полученная из доказуемых формул А и А В путем применения правила заключения, есть доказуемая формула. г)Никакая другая формула исчисления высказываний не считается доказуемой. Процесс получения доказуемых формул называется доказательством.

Пример доказательства 1. Доказать, что А А (рефлексивность импликации). Воспользуемся аксиомой A(I 2 ): (x(yz))((xy)(xz)) и выполним подстановку Тогда получим (x(yx))((xy)(xx))(1) Применяя правило заключения к аксиоме A(I 2 ) и формуле (1), получим (xy)(xx) (2)

Пример доказательства В формуле (2) осуществим подстановку В результате получим доказуемую формулу (3) Применим правило заключения к аксиоме А(IV 2 ) и формуле (3). Это приводит к доказуемой формуле xx(4) Наконец, осуществив подстановку в формуле (4) вместо х формулы А, получим AA

Пример доказательства 2. Доказать, что Возьмем аксиому (II 3 ) и выполним в ней последовательно две подстановки, заменяя сначала х на ¬х, а затем у на ¬у. В результате получим доказуемую формулу (z¬x)((z¬y)(z(¬x&¬y)))(1) В формуле (1) выполним подстановку Получим: