Алгебра логики
<<  Функциональное и логическое программирование Развитие логического мышления в процессе обучения младших школьников  >>
Дизъюнкция и ложь
Дизъюнкция и ложь
Приведение к нормальной форме
Приведение к нормальной форме
ПРИВЕДЕНИЕ К НОРМАЛЬНОЙ ФОРМЕ (продолжение)
ПРИВЕДЕНИЕ К НОРМАЛЬНОЙ ФОРМЕ (продолжение)
ПРИВЕДЕНИЕ К НОРМАЛЬНОЙ ФОРМЕ (продолжение)
ПРИВЕДЕНИЕ К НОРМАЛЬНОЙ ФОРМЕ (продолжение)
ПРИВЕДЕНИЕ К НОРМАЛЬНОЙ ФОРМЕ (окончание)
ПРИВЕДЕНИЕ К НОРМАЛЬНОЙ ФОРМЕ (окончание)
Равенство
Равенство
Равенство
Равенство
Правила для конъюнкции и истины
Правила для конъюнкции и истины
Правила для атомарных предикатов
Правила для атомарных предикатов
Правила для дизъюнкции
Правила для дизъюнкции
Корректные правила дизъюнкции
Корректные правила дизъюнкции
Корректные правила дизъюнкции
Корректные правила дизъюнкции
Правила для равенства
Правила для равенства
Явность
Явность
Явность
Явность
Явность
Явность
Явность
Явность
Явность
Явность
Явность
Явность
Явность
Явность
Явность
Явность
Явность
Явность
Явность
Явность
Явность
Явность
Явность
Явность
Явность
Явность
Явность
Явность
Явность
Явность
Явность
Явность
Явность
Явность
Явность
Явность
Завершенность
Завершенность
Завершенность
Завершенность
Завершенность
Завершенность
Унификация
Унификация
Унификация
Унификация
Картинки из презентации «Логическое программирование» к уроку алгебры на тему «Алгебра логики»

Автор: Igor. Чтобы познакомиться с картинкой полного размера, нажмите на её эскиз. Чтобы можно было использовать все картинки для урока алгебры, скачайте бесплатно презентацию «Логическое программирование.ppt» со всеми картинками в zip-архиве размером 227 КБ.

Логическое программирование

содержание презентации «Логическое программирование.ppt»
Сл Текст Сл Текст
1Логическое программирование. 26консеквент второго правила соответствует
Бэктрекинг. 1. цели. На какой вопрос мы должны ответить,
2Дизъюнкция и ложь. Попытаемся сделать чтобы прийти к этому утверждению? 26.
выбора правил явным. Для этого введем 27Унификация и поиск доказательств.
новые связки: дизъюнкцию и ложь Ложь это «Имеется такой экземпляр правила, что его
дизъюнкции нулевых альтернатив. 2. консеквент удовлетворяет цели». Мы можем
3Нормальная форма программ. Явная видеть, что эта спецификация не вполне
конъюнкция в программе – если каждое верна: нам необходимо конкретизировать
продукционное правило имеет в точности также и цель, поскольку S должно иметь
одну предпосылку. Но возможны несколько форму p(S1) для пока еще неизвестного S1.
правил для одной цели. Тогда следует Подцель в таком случае должна быть plus(0,
привести программу к нормальной форме. p(p(0)), S1) в соответствии с
Нормальная форма программ = программа в конкретизаций правила 0 для M, p(p(0)) для
явной дизъюнктивной форме. В таком случае N и S1 для S. 27.
каждая цель соответствует голове в 28Унификация и поиск доказательств.
точности одного правила. 3. «Существует экземпляр правила и экземпляр
4Приведение к нормальной форме. Это не цели такие, что они равны». Данная
явная дизъюнктивная форма потому что: Нет формулировка также несостоятельна.
утверждения для member(t, []) Для целей Например, подстановка p(p(p(p(0)))) для S
member(t, [t | ys]) могут быть применены в цели и S в правиле вместе с подстановкой
оба утверждения. 4. для M и N, как в предыдущем варианте,
5ПРИВЕДЕНИЕ К НОРМАЛЬНОЙ ФОРМЕ будет также делать цель и консеквент
(продолжение). Теперь оба правила имеют правила идентичными, но это абсолютно
одинаковый консеквент. Объединяем их неверно. Проблема в том, что здесь
дизъюнкцией: 5. заявляется больше, чем может быть сделано:
6ПРИВЕДЕНИЕ К НОРМАЛЬНОЙ ФОРМЕ использование S1 для S в правиле, с другой
(окончание). Теперь добавим утверждение стороны, оставляет переменную свободной.
для отсутствующего случая, с предпосылкой S1 будет детерминировано позже при поиске
ложь Программа приведена в явную и других унификациях. Чтобы обозначить
дизъюнктивную форму с предположением, что это, определяем, что t1 более общее, чем
второй аргумент – список. На Прологе: t2, если t1 может быть конкретизировано в
member(X, []) :- fail. member(X, [Y | Ys]) t2. 28.
:- X = Y ; member(X, Ys). 6. 29Унификация и поиск доказательств.
7Равенство. Вводное правило для «Найти более общий экземпляр правила и
высказывания , означающего, что s и t цели такие, что консеквент правила равен
равны: Мы также можем использовать s ? t, конкретизированной цели». В терминах
чтобы указать, что два терма различны, в подстановок это звучит так: найти ?1 и ?2
качестве вида рассуждения. 7. такие, что S’?1 = S?2, а любой другой
8Явный бэктрекинг. Программа экземпляр S’ и S это экземпляр S’?1. 29.
представлена в дизъюнктивной нормальной 30Унификация и поиск доказательств.
форме. Главный выбор – доказать A?B в «Сначала переименуем переменные в правиле
качестве цели. Операционная семантика таким образом, что они будут отличаться от
Пролога: сначала решить A и только если переменных в цели. Затем найдем одну,
решение завершится неудачей, решить B. К наиболее общую подстановку ?, которая
стеку цели S, мы добавляем другой аргумент унифицирует переименованный консеквент с
F, который хранит дальнейшие целью». Здесь унификация подстановки ?
(неиспользованные) возможности. F – является наиболее общей, если любая другая
продолжение неудачи (failure унифицирующая подстановка является
continuation). Записываем новое экземпляром ?. 30.
рассуждение как A / S / F и читаем его 31Подстановки. Подстановки ? ::=
так: Или А при S или F. Формально : If A / t1/x1,…,tn/xn Мы постулируем, что все xi
S / F then (A?S) ? F true. 8. уникальны. Порядок следования пар в
9Правила для конъюнкции и истины. Они постановках безразличен, и мы считаем
не меняются сильно, а только обеспечивают перестановки подстановок равными. Мы
продолжение неудачи. 9. обозначаем доменом (domain) от ? dom(?)={
10Правила для атомарных предикатов. Тоже x1,…,xn}. Похожим образом мы называем
простые, поскольку мы принимаем истинность множество переменных, встречающихся в
данных правила в явной дизъюнктивной выражении подстановки ti, со-доменом
форме. 10. (со-domain) в виде . 31.
11Правила для дизъюнкции. 32Подстановки. Допущение: Все
Доказательство: методом индукции на подстановки допустимы (valid), что
структуре дедукции для A / S / F. Мы означает dom(?)?cod(?) = ? для любой
должны показать, что если (A ? S)? (B ? F) подстановки ?. Это по большому счету
истина, то ((A ? B) ? S) ? F истина. единственный способ выполнения. Более
Раскрываем скобки: или A ? S истина, или В общее допущение – это то, что все
истина, или F истина. В среднем случае подстановки идемпотентны (идемпотентность
недостаточно информации, чтобы заключить, – свойство объекта, состоящее в том, что
что ((A ? B) ? S) ? F истина. любые действия над объектом не изменяют
Доказательство невозможно. 11. его), но мы верим, что вышеописанное более
12Корректные правила дизъюнкции. Мы удобно для наших ограниченных целей. 32.
должны объединить попарно альтернативу В 33Подстановки. Применение подстановки ?
со стеком цели S и восстановить S, когда к выражению t можно достаточно просто
мы делаем бэктрек, рассматривая В. Стек определить композиционно: x? = t если t/x
цели S’ во втором правиле отбрасывается, в ? y? = y если f(t1,…,tn) ? = f(t1 ?,…,tn
поскольку применяется к цели , которая не ?). 33.
может быть успешной. Вместо этого мы 34Композиция подстановок. Общее решение
восстанавливаем стек цели S, сохраненный с состоит в композиции этих двух
В. Здесь остался один случай, который не подстановок. Мы записываем это как ??.
покрыт правилами: нет правила для . Общая Главное свойство, которое нам нужно: для
цель терпит неудачу, если текущая цель любого t имеем (t?)?=t(??). Чтобы это
неудачна, и здесь нет дальнейших свойство могло поддерживать наши общие
альтернатив. 12. допущения о подстановках, мы специфицируем
13Правила для равенства. В Прологе предусловие, что dom(?)?dom(?) = ?. Мы
сложностей не вызывают. Мы всегда можем определяем композицию как подстановки
сказать, равны два терма или нет. 13. слева направо, пока не встретим пустую
14Явность. Теорема. Если A / S / F то (A подстановку (.). (t/x, ?) ? = t?/x, ?? (.)
?S)? F истина. Доказательство: С помощью = ? 34.
индукции на структуре D A / S / F. 14. 35Композиция подстановок. Теорема
15Явность. Случай 1: истина из гипотезы (композиция подстановок). Допустим, у нас
из инверсии первая часть дизъюнкции из есть выражение t и допустимые подстановки
двух инверсий из двух применений правила ? и ? при dom(?) ?dom(?)= ? и dom(?)
из правила ( ) F истина вторая часть ?cod(?)= ?. Тогда ?? допустимая
дизъюнкции из правила ( ). 15. подстановка и (??)? = t(??) Более того,
16Явность. Случай 2: Аналогичен если ? это подстановка, такая, что dom(?)
предыдущему случаю. Случай 3: из правила ( ?dom(?)= dom(?) ?dom(?)= ?, то также (??)?
) из правила ( ) из правила ( ). 16. = ?(??) Доказательство: Допустимость ??
17Явность. Случай 4: (B?S)?F истина уже была показана выше. Первое равенство
гипотеза из D’ B истина и S истина первый следует из индукции на структуре выражения
подслучай после инверсии P истина из t, второе – из индукции на структуре ?.
правила (P?S)?F истина из правил (?I и 35.
?I1) F истина второй подслучай после 36Композиция подстановок. Случай 1: t=x
инверсии (P?S)?F истина из правила (?I2). для переменной x. Тогда мы различаем два
17. подслучая. Подслучай: x dom(?) где s/x?.
18Явность. Случай 5: (A1 ?S)? ( (A2?S) (x?)? = s? по определению x? = x(??)
?F) из гипотезы в D1 A1 истина и S истина поскольку s?/x ?? Подслучай: x dom(?).
первый подслучай после инверсии A1 ? A2 (x?)? = x? по определению x? = x(??) по
истина из правила (?I1) ((A1 ? A2) ?S) ?F) определению ?? 36.
из правил (?I и ?I1) A2 истина и S истина 37Композиция подстановок. Случай 2:
второй подслучай после инверсии A1 ? A2 t=f(t1,…,tn) для выражений t1,…,tn. (t?)?
истина из правила (?I2) ((A1 ? A2) ?S) ?F) = f(t1?,…,tn) для выражений t1,…,tn по
из правил (?I и ?I1) F истина третий определению t? = f((t1?)?,…,(tn?)?) по
подслучай после инверсии ((A1 ? A2) ?S) определению f(_)? = f((t1(??),…,(tn (??))
?F) из правила (?I2). 18. и т.д. n раз =f(t1,…,tn)(??)=t(??) по
19Явность. Случай 6: (A2 ? S1)?F0 истина определению t(??). 37.
из гипотезы D2 (?S)?((A2?S1) ? F0) истина 38Унификация. Допустим ? это унификатор
из правила (?I2) Остальные случаи: t и s, если t?=s?. Мы говорим, что ? это
Докажите дома. 19. наиболее общий унификатор для t и s, если
20Завершенность. Данный набор правил не он является унификатором, а для любого
является завершенным. Например, такое другого унификатора ? существует
правило Не может быть найдено с помощью подстановка ?’ такая, что ? = ??’. Другими
поиска, поскольку нет доказательства даже словами, унификатор является наиболее
если есть простое доказательство, что общим, если любой другой унификатор
diverge истина: 20. является его экземпляром, где «экземпляр»
21Метаинтерпретатор для явного это композиция подстановок. 38.
бэктрекинга. True, true, _, istrue). 39Унификация. Рассуждение имеет форму t
Solve(true, (A , S), F, J) :- solve(a, S, s | ?, где t и s – входы, а наиболее общий
F, J). Solve((a,b), S, F, J) :- solve(a, унификатор ? – выход. Чтобы обойти n-
(B, S), F, J). Solve(fail, _, fail, арную природу списка аргументов, мы будем
isfalse). Solve(fail,_,((b,s) ; F), J) :- иметь внешнее рассуждение t s | ? для
solve(b,s,f,j). Solve((a ; B),S,F,J):- последовательностей выражений t и s
solve(a,s,((b,s) ; F), J). Solve((x = Применение подстановок может расширяться
Y),S,F,J) :- X = Y, solve(true,s,f,j). до последовательности выражений очевидным
Solve((x = Y),S,F,J) :- X \= Y, способом. Мы используем (.) в качестве
solve(fail,s,f,j). Solve(p,s,f,j) :- пустой последовательности выражений (а
clause(p,b), solve(b, S, F, J). % также для пустой подстановки, являющейся
Интерфейс верхнего уровня solve(a, J) :- последовательностью выражений и пар
solve(a, true, fail, J). 21. переменных).. 39.
22Метаинтерпретатор для явного 40Унификация. Вначале рассмотрим
бэктрекинга. Имея программу в явной функциональные выражения и
дизъюнктивной форме, такую, как member(X, последовательности выражений. Затем,
[]) :- fail. member(X, [Y|Ys]) :- X = Y ; случаи переменных. 40.
member(X, Ys). мы можем задать цель: ?- 41Унификация. Условие, что t = f(t) в
solve(member(1, [2,3,4]), J). J = isfalse; последнем правиле гарантирует, что оно не
?- solve(member(1, [1,2,1,4]), J). J = пересекается с правилом для x t. Условие,
istrue; Каждый запрос будет завершаться что x FV(t) необходимо потому, что,
успехом только один раз, поскольку наш например, два выражения x и f(x) не имеют
метаинтерпретатор находит только первое унификатора: неважно, что подстановка
решение. 22. f(x)? всегда имеет на одно появление f
23Абстрактные машины. Анализируя больше, чем x?, и поэтому они не могут
правила, мы можем видеть, что для каждого быть равными. Другая ситуация, когда
состояния имеется уникальное унификация терпит неудачу – это уравнение
преобразование состояния, за исключением: в форме f(t) = g(s) для f ? g, и две
Состояние является финальным, поскольку не последовательности выражений имеют разную
существует предпосылок, удовлетворяющих длину. Последнее может случиться, если
правилу. Вычисление завершается. Состояние функции имеют разную арность, и в таком
является финальным, поскольку нет правил, случае неудача унификации это корректный
которые можно применить. Вычисление результат. 41.
заканчивается неудачей. Состояние P/S/F 42Явность. Теорема. Если t s | ? то t? =
вызывает уникальное преобразование (в s?. Доказательство: Нам нужно обобщить
соответствии с требованием, что естm это, чтобы покрыть рассуждение внешней
уникальное правило для каждой атомарной унификации на последовательности
цели P), правда, как найти экземпляр выражений. Если t s | ? то t? = s?. Если t
правила, остается неформальным. 23. s | ? то t? = s?. Доказательство
24Основные понятия на сегодня. выполняется с помощью взаимной индукции на
Нормальная форма программ Явный бэктрекинг структуре дедукции D от t s и E от t s.
Явность Завершенность Абстрактные машины. Это означает, что если одно рассуждение
24. появляется в качестве предпосылки правила
25Логическое программирование. для другого, мы можем применить подходящую
Унификация. 25. гипотезу индукции. 42.
26Унификация и поиск доказательств. 43Основные понятия на сегодня.
Пусть есть унарное сложение И атомарная Унификация Подстановки Композиция
цель plus(p(0), p(p(0)), S). Только подстановок Явность. 43.
Логическое программирование.ppt
http://900igr.net/kartinka/algebra/logicheskoe-programmirovanie-135152.html
cсылка на страницу

Логическое программирование

другие презентации на тему «Логическое программирование»

«Логические операции» - А, В – логические переменные, которые могут иметь значение ИСТИНА (И), ЛОЖЬ (Л). Порядок заполнения строк для исходных столбцов: 1-й столбец. Приоритет выполнения логических операций (если нет скобок). Простые высказывания могут быть связаны между собой словами И, ИЛИ, НЕ. В следующих столбцах – значения истинности последовательно выполняемых операций и окончательного результата.

«Логическое мышление» - Петя, Нина, Надя, Вова и Юра играли в прятки. Особенности речи и мышления у детей с ОНР: Чего не бывает? Что на что похоже? Основные формы логического мышления. Чувственное познание абстрактное мышление. Сравнение, обобщение, группировка, классификация Сравнение предметов и явлений по свойствам и качествам.

«Логические функции» - № 3.4. Доказать, пользуясь ТИ, что операция эквивалентности равносильна выражению. 2. Графический. В противном случае можно прийти к ложному умозаключению. Следовательно получится функция: Так возникла формальная логика. Логические основы вычислительной техники. Физики. Лампочка горит, если включен хотя бы один выключатель.

«Решение логических задач» - Павлов - баянист. Синицын – художник; Требуется определить кто есть кто. Табличный способ решения логических задач. Фамилии: Воронов, Павлов, Журавлев, Синицын. Синицын - художник. Воронов. Воронов и Журавлев не баянисты. Журавлев-писатель. Воронов - математик. По таблице видно, что Воронов математик.

«Логические таблицы истинности» - Установить последовательность выполнения логических операций. Таблица истинности сложного логического выражения. Заполнить таблицу истинности по столбцам. Выяснить количество столбцов = количество переменных + количество логических операций. Таблицы истинности. Для составления таблицы необходимо: Как правильно составить и использовать?

«Упростить логическое выражение» - Найдите X, если По закону де Моргана. По закону исключенного третьего В v ¬В = 1, следовательно А ^ (В v ¬B) = А ^ 1 = А. Воспользуемся правилом дистрибутивности и вынесем за скобки А: (А ^ В) v (А ^ ¬В) = А ^ (В v ¬В). Пример 2. Упростить логическое выражение: не(А или В)= не А и не В не(А и В)= не А или не В.

Алгебра логики

19 презентаций об алгебре логики
Урок

Алгебра

35 тем
Картинки
900igr.net > Презентации по алгебре > Алгебра логики > Логическое программирование