Л ОГИКА ПРЕДИКАТОВ. С ВОЙСТВА ФОРМАЛЬНЫХ ТЕОРИЙ Общезначимость Непротиворечивость Полнота Разрешимость Независимость. - презентация

1 Л ОГИКА ПРЕДИКАТОВ

2 С ВОЙСТВА ФОРМАЛЬНЫХ ТЕОРИЙ Общезначимость Непротиворечивость Полнота Разрешимость Независимость

3 О КОРРЕКТНОСТИ ИВ (A(BC))((AB)(AC)) A(BC) - И, (AB)(AC) – Л (AB) - И, а AC – Л. A истинна, а C ложна A, (AB) и (A(BC)) истинны. B и (BC) истинны C истинна – противоречие

4 О ПОЛНОТЕ ИВ Лемма 1. Какова бы ни была формула D, формула (DD) является теоремой. 1. (D((DD)D))((D(DD))(D)) [акси ома 2 при A=D, B=(DD), C=D]; 2. D((DD)D) [аксиома 1]; 3. (D(DD))(DD) [из 1 и 2 по правилу MP ]; 4. D(DD) [аксиома 1]; 5. (DD) [из 3 и 4 по правилу MP ].

5 Л ЕММА О ДЕДУКЦИИ Пусть Г – множество формул. Тогда Г АB тогда и только тогда, когда Г {A} B.

6 Л ОГИКА ПРЕДИКАТОВ Маша любит кашу Даша любит кашу Саша любит кашу Х любит кашу Х {Маша, Даша, Саша}

7 П РЕДИКАТ P ( a ) – логическое высказывание a – обладает свойством P, a принадлежит множеству объектов, которые обладают свойством P. Например: Конфуций принадлежит множеству смертных. Такое высказывание элементарно.

8 М ЕСТНОСТЬ Множество истинности P + предиката P(x), определенного на базовом множестве M (x M), называется множество тех элементов x M, для которых P(x) истинно. Примеры высказывательных форм: 2k, m + n,, m>n+1 и др. Рассмотрим двуместную высказывательную форму: x³y+2. Пусть x определено на множестве M x ={3;5}, y – на множестве M y ={1;5;8}. Этой форме соответствуют два предиката. Один P 1 задан на множестве, образованным декартовым произведением X 1 = M x M y Другой P 2 задан на множестве, образованным декартовым произведением X 2 = M y M x

9 К ЛАССИФИКАЦИЯ ПРЕДИКАТОВ Предикат называется выполнимым, если существует хотя бы один набор предикатных переменных, при которых он обращается в истинное высказывание. Предикат называется опровержимым, если существует хотя бы один набор предметных переменных, при которых он превращается в ложное высказывание. Тождественно-истинным называется предикат, если для любого набора предикатных переменных он является истинным высказыванием. Тождественно-ложным называется предикат, если для любого набора предикатных переменных он является ложным высказыванием.

10 Р АВНОСИЛЬНОСТЬ И СЛЕДСТВИЕ

11 Т ЕОРЕМЫ Пусть из P Q, т.е. Q следствие P, тогда если P – тождественно-истинно (выполнимо), то и Q – тождественно-истинно (выполнимо). Если Q – тождественно-ложный (опровержимый) предикат, то и P – тождественно-ложный (опровержимый) предикат.

12 К ВАНТОРЫ Квантор общее название для логических операций, ограничивающих область истинности какого- либо предиката. Квантор существования (обозначение:, читается: «существует…» или «найдётся…»). x(Рn(x))

13 П РИМЕРЫ x(P 1 (x)):= "cуществуют целые числа, которые являются простыми". Это условие выделяет на множестве целых чисел подмножество X = {2, 3, 5, 7, 11, 13, 17,...}, для которого предикат P1(x) принимает значение и. y(P 2 (6,y)):="существуют числа y, которые меньше 6". Это условие выделяет на множестве целых чисел подмножество Y= {1, 2, 3, 4, 5}, для которого предикат P 2 (6,y) принимает значение и. y(P 3 (6,2,z)):="существует число z, которое является частным от деления 6 на 2". Это условие выделяет на множестве целых чисел единственное число Z=3, для которого предикат P 3 (6,2,z) принимает значение и. Если P 7 (x):="x имеет зачетную книжку", то x(P 4 (x)& P 7 (x)):= "существуют студенты (x), которые не имеют зачетной книжки"; x y(P 5 (x,y)& P 7 (x)):="существуют студенты (x) некоторых университетов (y), которые не имеют зачетной книжки".

14 К ВАНТОРЫ Квантор всеобщности (обозначение:, читается: «для всех…», «для каждого…» или «каждый…», «любой…», «для любого…»). x, y, z,... (P n (x, y, z,...)).

15 П РИМЕРЫ x(P 4 (x)&P 7 (x)):= "все (или каждый) студенты (x) имеют зачетную книжку"; x(P 5 (x, СГТУ)&P 7 (x)):="все (или каждый) студенты (x) университета СГТУ имеют зачетную книжку"; x y(P 5 (x,y)&P 7 (x)):="все (или каждый) студенты (x) всех (или каждого) университетов (y) имеют зачетную книжку"; x y(P 2 (x, y)):= "для всех целых чисел x существует меньшее число y". x y z(P 3 (x, y, z)):="для всех целых чисел x и y существует число z, которое является частным от деления x на y".

16 К ВАНТИФИКАЦИЯ x P(x) x y P(x,y,z) х у ( Р(х,у)) Q(у,z)

17 П РАВИЛА ВЫВОДА

18 П РИМЕР Показать выводимость формулы r из посылок p q, q r, p

19 У СЛОВНО - КАТЕГОРИЧНЫЕ УМОЗАКЛЮЧЕНИЯ Modus ponens Modus tollens

20 Р АЗДЕЛИТЕЛЬНО - КАТЕГОРИЧНЫЕ РАССУЖДЕНИЯ Modus tolledo Modus ponendo tolens Некорректно

21 У СЛОВНО РАЗДЕЛИТЕЛЬНЫЕ УМОЗАКЛЮЧЕНИЯ

22

23

24 Сложная конструктивная дилемма Простая деструктивная дилемма Сложная деструктивная дилемма