Файл: Основные положения исчислений Учебные вопросы.pptx

СОДЕРЖАНИЕ

Основные положения исчислений

Учебные вопросы

1. Традиционная логика (Элементы силлогистики)

Схема классического представления связи между теорией, эмпиризмом, индукцией и дедукцией.

Индуктивный метод

Схема полной индукции

Множество А состоит из элементов: a1, a2, a3, …, an.

Все элементы от a3 до an также имеют признак В

Следовательно Все элементы множества А имеют признак В.

Пример метода полной индукции

Схема неполной индукции

Схема неполной индукции: Множество А состоит из элементов: a1, a2, a3, … ak, … an.

Все элементы от a3 до ak также имеют признак B

Следовательно Вероятно, ak+1 и остальные элементы множества А имеют признак В.

Пример неполной индукции

Определение дедукции и дедуктивного метода

Понятие «силлогистика» и «силлогизм»

Формы силлогизмов

Категорический силлогизм

Пример силлогизма

Общие правила простого категорического силлогизма (Википедия)

Правила терминов

Фигуры силлогизма

Классификация высказываний (суждений, пропозиций)

Связь между высказываниями

Типы высказываний (суждений)

Логический квадрат

Правильные модусы простого категорического силлогизма

Примеры правильных модусов

Barbara

Все животные смертны. A

Все люди — животные. A

Все люди смертны. A

Celarent

Ни одна рептилия не имеет меха. E

Все змеи — рептилии. A

Ни одна змея не имеет меха. E

Darii

Все котята игривые. A

Некоторые домашние животные — котята. I

Некоторые домашние животные — игривые. I

Ferio

Ни одна домашняя работа не весела. E

Некоторое чтение — домашняя работа. I

Некоторое чтение не весело. O

Обозначение умозаключения

Пример слабого силлогизма

Barbari

Все животные смертны. A

Все люди — животные. A

некоторые люди смертны. I

Диаграммы Эйлера

Диаграммы Эйлера

Фигуры условно-категорического силлогизма

Условно-категорический силлогизм

2. Основные положения исчислений

2.1. Определение формальной системы (исчисления)

Определение формальной системы

Формальные языки и формальные грамматики

Порождающая грамматика

Нотация Бекуса-Наура

Пример нотаций Бекуса

Вывод формулы

Основные понятия исчислений

Требования к аксиомам

Теорема о неполноте Геделя

2.2 Исчисление высказываний

Состав формальной системы

Исчисление высказываний

Системы аксиом исчисления высказываний

Правила вывода исчисления высказываний

2.3. Методы доказательства теорем

Методы доказательства теорем

С помощью таблицы истинности

С помощью логических преобразований

С помощью таблицы истинности

Методы доказательства теорем. Метод Вонга

Пусть дана клауза в своей наиболее общей форме:

В1, В2, …, Вn  А1, А2, …,Am

Шаг 2. Если слева от символа  встречается конъюнкция, а справа дизъюнкция, то их следует заменить на запятые.

Пример доказательства методом Вонга

Пример доказательства

Метод резолюции

Метод резолюции

1. Запишем формулу связи импликации и выводимости логической формулы:

 (А&В&С&…Ф)

2.Избавимся от импликации:

 ((А&В&С&…)Ф)

3.Применим закон де Моргана:

 ( (А&В&С&…)Ф))

4.Поскольку данная формула выводима (знак ), верна формула

 (А&В&С&…Ф)=T,

следовательно, отрицание (А&B&C&…Ф)=F.

Алгоритм вывода по методу резолюции

Шаг 1: принять отрицание заключения, т.е. ¬Ф,

Шаг 2: привести все формулы посылок и отрицания заключения в КНФ,

Шаг 3: сформировать множество К дизъюнктов всех посылок и отрицания заключения: K = {D1, D2, …, Dk},

Силлогизм Modus ponens

Метод линейной резолюции

Дизъюнкты Хорна

Фразы Хорна. В прямом методе вывод проводился исходя из свойств связок и из того, что предметная область описывалась через импликацию, конъюнкцию, дизъюнкцию и отрицание.

Дизъюнктом Хорна называется дизъюнкт, содержащий не более одного положительного литерала.

Дизъюнкт ровно с одним положительным литералом – определенный дизъюнкт.

Дизъюнкт – ровно с одним отрицательным литералом – целевой дизъюнкт.

Язык Prolog (википедия)

Язык логического программирования Prolog

Дизъюнкты Хорна

% Some simple test Prolog programs

% --------------------------------

% Knowledge bases

loves(vincent, mia).

loves(marcellus, mia).

loves(pumpkin, honey_bunny).

loves(honey_bunny, pumpkin).

jealous(X, Y) :-

loves(X, Z),

loves(Y, Z).

/**

?- loves(X, mia).

?- jealous(X, Y).

*/

Prolog-program

% Constraint Logic Programming

:- use_module(library(dif)). % Sound inequality

:- use_module(library(clpfd)). % Finite domain constraints

:- use_module(library(clpb)). % Boolean constraints

:- use_module(library(chr)). % Constraint Handling Rules

:- use_module(library(when)). % Coroutining

%:- use_module(library(clpq)). % Constraints over rational numbers

% Your program goes here

x1.

x2.

x3:-x1.

/** Your example queries go here, e.g.

?- x3.

*/

3. Исчисление предикатов первого порядка

3.1 Определение предиката

Понятие предиката

Предикаты могут принадлежать к следующим семантическим типам:

Определение предиката

Классификация предикатов

Интерпретация предикатов

Логические операции над предикатами

Операции связывания предикатов

Примеры предикатов

Примеры предикатов

Пример 1: «Всякий человек смертен» - х (Человек(х)  Смертен(х))

Пример 2: «Всякий студент изучает какую-нибудь предмет» - х (Студент(х)  у Наука(у)&Изучает(х,у))

Пример 3: «Квадрат любого четного числа больше 1»- х(Четное_число(х)>(Квадрат(х),1)).

Типы суждений (высказываний)

Законы алгебры предикатов

Примеры использования кванторов

3.2. Определение формальной системы предикатов первого порядка

Алфавит формальной системы Исчисление предикатов

Алфавит формальной системы.

Формулы формальной системы

Введем понятие формулы в исчислении предикатов:

Аксиомы исчисления предикатов

Правила вывода

Правила для кванторов

Правила преобразования формул

3.3. Метод резолюции

Предваренная нормальная форма формулы исчисления предикатов

Алгоритм приведения к предваренной нормальной форме

Пример приведения к предваренной нормальной форме

Алгоритм приведения к ССФ:

Пример получения сколемовской стандартной формы

∀x ∃ y∀t ∃q (P(x) & (¬Q(t, y) & ¬ R(a, t, q)).

Операция подстановки

Алгоритм подстановки

Пример. Найти НОУ для W = {P(y, g(z), f(x)), P(a, x, f(g(y)))}.

1) 0 = и W0 = W.

2) так как W0 не является одноэлементным множеством, то перейти к пункту 3.

3) {у, а}, т. е. {а/у}.

4) 1 =0{а/у} =  {а/у} = {а/у}.

W1= W0 {а/у} = { P(a, g(z), f(x)), P(a, x, f(g(a)))}.

5) так как W1 опять неодноэлементно, то множество рассогласований будет {g(z),x}, т. е. {g(z)/x}.

6) 2 =1{g(z)/x} = {а/у, g(z)/x},

W2= W1 { g(z)/x } = { P(a, g(z), f(g(z))), P(a, g(z), f(g(a)))}.

7) имеем {z, a},{z/ a}.

8) 3 =2{z, a} = {а/у, g(z)/x, a/z},

W3= W2 {a/z } = { P(a, g(a), f(g(a))), P(a, g(a), f(g(a)))}= { P(a, g(a), f(g(a)))},

3=2{a/z} = {а/у, g(z)/x, a/z} есть НОУ для W .

Метод резолюции

Пример резолюции

Метод резолюции