Логическое и функциональное программирование
Знание того, что А и В есть истина, должно означать, что А есть истина и В есть истина.
3.Интродукция ИЛИ:
![]()
Если А есть истина, то А или В есть истина. То же самое имеет место, если В есть истина.
4.Интродукция И:
![]()
Если А есть истина и В есть истина, то А И В есть истина.
5.Двойное отрицание:
![]()
Если А есть не не истина, то А есть истина.
6.Единичная резолюция:
![]()
Если А или В есть истина и не В, то А есть истина. Точно также, если не А, то В – истина.
7.Резолюция:
![]()
Если А или В и не В или С, то, поскольку В не может быть истинно и ложно одновременно, должно быть А или С истинно.
Пример: Имеется следующая информация.
Если аккумулятор машины разряжен, то машина не заводится. Если машина Ивана не заводится и текущее время оказывается позже восьми часов утра, то Иван опоздает на поезд. Однажды после восьми утра аккумулятор Ивана оказался разряженным.
Используя логические правила вывода, доказать, что Иван опоздает на поезд.
В символьных обозначениях информация может быть представлена в следующем виде:
P: аккумулятор разряжен.
Q: машина не заводится.
R: время после восьми утра.
S: Иван опоздал на поезд.
Правило 1: P ® Q.
Правило 2. QЩR ® S.
Известно, что P и R есть истина. Задачей является доказать S. Доказательство строится следующим образом:
P – дано.
R – дано.
Q следует из 1 и правила 1 по правилу modes ponens.
QЩR следует из 3 и 2 по правилу интродукции И.
S следует из 4 и правила 2 по правилу modes ponens.
Исчисление предикатов предполагает, что мир можно моделировать с помощью фактов. Но для реальных приложений исчисления высказываний недостаточно.
Практические задания
Задание 1
Даны логические функции:

Получить значения этих функций с помощью таблиц истинности. Преобразовать к алгебраическому виду и определить значения для x =1, y =1, z = 0. Преобразовать к виду с использованием только операций дизъюнкции, конъюнкции и отрицания. Упростить. Привести к СДНФ и СКНФ. Восстановить СДНФ и СКНФ по таблице истинности. Построить импликантную таблицу и определить сокращенную ДНФ с использованием метода Петрика. Минимизировать с использованием алгоритма Квайна и диаграммы Вейча.
Задание 2
Если собака видит кошку, то она за ней гонится. Если за котом Васькой гонится собака и рядом есть дерево, то кот Васька забирается на дерево. В саду много деревьев. Однажды, в саду Ваську увидела собака.
Доказать, пользуясь логическими правилами вывода, что Васька забрался на дерево.
Компьютерное задание
Реализовать программу решающую следующую задачу:
На входе программы – таблица истинности для функции четырех переменных.
На выходе программы – СДНФ, СКНФ, диаграмма Вейча и минимальная нормальная форма.
2.2 Исчисление предикатов
Исчисление предикатов расширяет язык исчисления высказываний так, что мир оказывается, состоящим из объектов, отношений и свойств.
Логику предикатов можно рассматривать как компоненту естественного языка, имеющую в соответствии со сложностью синтаксических правил иерархическую структуру, которую образуют предикаты первого порядка, второго и так далее. Для логики предикатов определено множество значений и на его основе определены слова как последовательности знаков. Функцией языка предикатов является задание слов двух типов:
Слова, задающие сущности изучаемого мира.
Слова, задающие атрибуты / свойства этих сущностей, а также их поведение и отношения.
Первый тип слов называется термами, второй – предикатами.
Некие сущности и переменные определяются упорядоченными последовательностями конечной длины из букв и символов, исключая зарезервированные. Константы и переменные определяют отдельные объекты рассматриваемого мира. Последовательность из n констант или переменных (1 Ј n < Ґ), заключенная в круглые скобки, следующие за символом функции, имя которой задано некоторой конечной последовательностью букв, называется функцией.
Например, функция f(x, y) принимает некоторые значения, которые определяются значениями констант и переменных (аргументов функции), содержащимися под знаком функции. Эти значения, так же как и аргументы, являются некоторыми сущностями рассматриваемого мира. Поэтому все они объединяются общим названием терм (константы, переменные, функции).
Атомарным предикатом (атомом) называется последовательность из n (1 Ј n <Ґ) термов, заключенных в круглые скобки, следующие за предикатным символом, имя которого выражается конечной последовательностью букв. Предикат принимает одно из двух значений true или false в соответствии со значениями, входящих в него термов.
Предикат @ Нераспространенное простое предложение
Из атомов с помощью, выполняющих функции союзов, символов составляются логические формулы, соответствующие сложным предложениям. В логике предикатов используются два класса символов. Первый класс соответствует союзам и включает операции дизъюнкции, конъюнкции, отрицания, импликации и эквивалентности.
Символы первого класса позволяют определять новый составной предикат, используя уже определенные предикаты. Различие между символами первого класса лежит в правилах, в соответствии с которыми определяются значения истинности или ложности составного предиката в зависимости от истинности или ложности элементарных предикатов. Символы ® и », вообще говоря избыточны так, как:

но используются т.к. ® эквивалентен фразе «Если А, то В», а » - «А и В эквивалентны».
В качестве
символов второго
класса используются
" и $.
Эти символы
называются
кванторами
общности и
существования,
соответственно.
Переменная,
которая квантифицирована,
т.е. к ней применен
один из кванторов
,
называется
связанной.
Квантор общности
является обобщением,
аналогом конъюнкции,
а квантор
существования
– обобщением,
аналогом дизъюнкции
на произвольное,
не обязательно
конечное множество.
Действительно,
пусть
Тогда для любого
предиката U
выполняется:

Аналогом законов Де Моргана для кванторов являются:

Часто возникает ситуация, когда некоторые переменные связываются кванторами ", а все другие - $. В этом случае может возникнуть неоднозначность при интерпретации кванторов.
Пусть задан некоторый предикат U(x, y). Очевидно, что возможно восемь случаев связывания его кванторами существования и общности:

Необходимо дать интерпретацию этим восьми случаям.
Рассмотрим, например, предикат подсистема(x, y), который задает отношение x подсистема y. Пусть переменная x связана квантором общности, а y – квантором существования. В этом случае существует две интерпретации: 1. «Для всех x, существует y, для которых x подсистема», 2. «Существует y, что все x его подсистемы».
Порядок следования связанных квантором переменных определяется при чтении предиката слева направо. Дадим интерпретацию для других значимых случаев, которые можно выразить этим предикатом и кванторами:
("x)($y)подсистема(x, y) – все объекты являются подсистемами;
($x)("y)подсистема(x,y) – существует объект, который является подсистемой любого объекта;
("y)($x)подсистема(x, y) – для всякого объекта существует объект, являющийся его подсистемой;
("x)($y)подсистема(x, y) – существует объект, который является чей-то подсистемой.
Сделаем некоторые важные обобщения.
1.Чтобы найти отрицание выражения, начинающегося с кванторов, надо каждый квантор заменить на его двойственный и перенести знак отрицания за кванторы. Отсюда:
![]()
2.Одноименные кванторы можно переставлять. Разноименные кванторы можно переставлять только в одну сторону. Отсюда:
![]()
Если
то
![]()
Действительно, если существует объект, который является чьей-то подсистемой, то для каждого объекта будет существовать объект, являющийся его подсистемой.
Если
то
![]()
Действительно, если существует y, что все x его подсистемы, то для всех x существует y, для которого x подсистемы. Однако, перестановка в обратную сторону неверна. Например:
Если
то
необязательно.
Действительно, если для каждого объекта существует объект, являющийся его подсистемой, то это не означает, что существует объект, который является чьей-то подсистемой.
3.![]()
Докажем эту равносильность.

В этой выкладке мы опирались на следующее утверждение:
![]()
Определение ППФ и семантика логики предикатов
Комбинируя два типа символов, можно рекурсивно определить составную формулу логики предикатов, называемую правильно построенной формулой (ППФ) или логической формулой.
Атомарный предикат является ППФ.
Если
F и G
являются ППФ,
то
также ППФ.
Если F(x) – ППФ, то ("x)F(x) и ($x)F(x) – ППФ.
Все результаты, полученные применением конечного числа раз (1) – (3) являются ППФ. Ничто другое не является ППФ.
Формулы логики предикатов строятся безотносительно к понятиям задаваемой предметной области. Если решено, что этими формулами будет описываться конкретная предметная область, то должно быть установлено соответствие между понятиями предметной области и этими формулами. Это предполагает следующие действия:
Устанавливаются соответствия между константами логики предикатов и сущностями этой области. Константы є Имена объектов.
Устанавливаются соответствия между формулами и функциональными отношениями предметной области.
Устанавливаются соответствия между атомарными предикатами и концептуальными отношениями предметной области.
Таким образом, в язык приносится конкретное смысловое содержание, то есть семантика логики предикатов. Обычно такая интерпретация формально представляется следующим образом:
Задается непустое множество D, определяющее сущности рассматриваемой предметной области, и элементы из D определяются как константы или переменные.
Для
функций (функциональные
отношения),
определенных
на множестве
аргументов
от
до D назначаются
функциональные
символы.
Каждому предикату n переменных назначается отношение, определенное на Dn, и его значение – True или False.
Множество D, рассматриваемое с позиций логики предикатов, называется областью переменных.
Значения ППФ оцениваются следующим образом:
Если
известны значения
логических
формул F
и G, то значения
оцениваются
по таблице
истинности.
Если для всех xОM F оценивается как истина, то истиной является ("x)F(x).
Если хотя бы для одного xОM F оценивается как истина, то ($x)F(x) тоже истина.
Предложения
Когда все переменные предиката являются связанными, то такой предикат называется предложением. Различие между ППФ, являющимися и не являющимися предложениями, состоит в том, что предложениям можно однозначно поставить в соответствие значение True или False, в то время как во втором случае нельзя непосредственно по виду формулы вынести суждение об ее истинности или ложности. Например, предикатная формула подсистема (x, y) не является предложением. Если в нее подставлены определенные значения, например, x = процессор, y = ЭВМ, то выражение подсистема (процессор, ЭВМ) принимает значение True, а при подстановке x = человек, выражение подсистема(человек, ЭВМ) является False. То есть истинность или ложность предикатной формулы можно оценить тогда и только тогда, когда в переменные подставлены некоторые конкретные сущности (в этом случае формула называется высказыванием). Отметим, что значение предикатных формул со связанными переменными можно определить, и не производя такого рода подстановки.
Например,
- у каждого человека
имеется отец
– является
истиной, а
- любой является
чьим-то отцом
– является
ложью.
Предположим, что имеется некоторое множество логических формул S. Если существует такая интерпретация, что все эти формулы принимают значение истина, то подобная интерпретация называется моделью. Например, рассмотрим множество:

Тогда интерпретация вида (человек (Сократ) = True) и (смертен (Сократ) = True) – является моделью так как все логические формулы S есть истина. Не обязательно, что такая модель единственна.
Пусть имеется некоторая группа S логических формул. Если для всех моделей S некоторая логическая формула s есть истина, то принято говорить, что s является логическим заключением (консеквентом) в S. Факт реализации логического консеквента записывается в виде SЅ=s.
Правила вывода логики предикатов
Вывод представляет собой процедуру, которая из заданной группы выражений выводит, отличное от заданного выражение. Когда группа выражений, образующих посылку, является истиной, то должно гарантироваться, что выражение, выведенное из них в соответствии с правилом вывода, также является истиной.
В логике предикатов в качестве такого правила вывода используется правило, которое из двух выражений A и A®B выводит новое выражение B. Это правило называется правилом дедуктивного вывода.
Для описаний правил вывода во многих случаях используется нотация (как это указывалось выше), при которой над чертой записывается группа выражений, принимаемых за посылку, а под чертой – выражение, которое выводится:
![]()
Такой тип правила вывода носит название modus ponens.
Можно
многократно
использовать
одно и тоже
правило вывода.
Например, если
помимо выражений
A, A®B
существует
выражение B®C,
то можно вывести
C, дважды
использовав
приведенное
правило. Получение
выражения s
применением
конечного числа
раз правила
вывода к заданной
группе выражений
S будем
записывать
в виде:
При этом говорят, что s дедуктивно выводится из S. Очевидно, что из вышеуказанного, легко выводится еще одно правило:
![]()
Практические задания
Задание 1. Задан предикат выполнение(x, y) , который задает отношение «y является результатом выполнения программы x». Дать интерпретацию утверждений:
("x)($y)выполнение(x,y);
($x)("y) выполнение(x,y);
("x)("y) выполнение(x,y);
($x)("y) выполнение(x,y);
("y)($x) выполнение(x,y);
($x)($y) выполнение(x,y).
Задан предикат реализация(x, y), который означает «программа x реализована на языке y». Записать утверждения:
А) Существует программа, реализованная на Паскале, имеющая в качестве результата 1000.
Б) Любая программа, написанная на C, дает результат.
3. Функциональное программирование
Функциональное программирование представляет собой модель индуктивного вывода, реализуемую с помощью рекурсивных процедур, l-исчисления и списковых структур.
3.1 Индуктивный вывод
Индуктивный
вывод – это
вывод из имеющихся
данных, объясняющего
их общего правила.
Например, пусть
известно, что
есть некоторая
функция от
одной переменной.
Рассмотрим
как выводится
f(x), если
последовательно
задаются в
качестве данных
пары значений
(1, f(0)), (1, f(1)).
Вначале задается
(0, 1) и имеет смысл
ввести постоянную
функцию f(x)
= 1. Затем задается
пара (1, 1), которая
удовлетворяет
f(x)=1.
Следовательно,
нет необходимости
менять вывод.
Пусть теперь
задается (2, 3). Это
не согласуется
с нашим выводом.
Предположим,
что методом
проб и ошибок
удается найти
.
Она удовлетворяет
заданным до
сих пор фактам.
Далее, если
будут следовать
факты (3, 7), (4, 13), (5, 21), …,
убедимся в
справедливости
предшествующего
вывода. Таким
образом в индуктивном
выводе в каждый
момент времени
объясняются
все данные,
полученные
до этого момента.
Если данные,
позже, перестанут
удовлетворять
полученному
выводу, то его
придется менять.
Следовательно,
индуктивный
вывод – это
неограниченно
долгий процесс.
Для определения индуктивного вывода необходимо уточнить:
Множество правил объектов вывода.
Метод представления правил.
Способ показа примеров.
Метод вывода.
Критерий правильности вывода.
В качестве правил – объектов вывода можно рассматривать:
функции;
грамматики языков;
программы.
Метод представления удобно организовывать в виде пар (x, f(x)), последовательности действий, вычисляющих f(x) и т.д.
Вывод реализуется благодаря неограниченному повторению процесса:
Запрос входных данных ® предположение ® выходные данные.
Критерием правильности вывода считается идентификация в пределе. Говорят, что машина вывода M идентифицирует в пределе правило R, если при показе примеров правилу R последовательность выходных данных, генерируемых M, сходится к некоторому представлению t, а именно: все выходные данные, начиная с некоторого момента времени, совпадают с t, при этом t называют правильным представлением R. Кроме того, говорят, что множество правил G позволяет сделать индуктивный вывод, если существует некоторая машина вывода M, которая идентифицирует в пределе любое правило R из множества G.
Характерным примером индуктивного вывода является математическая индукция.
3.1.1 Математическая индукция
Методом математической индукции называются утверждения вида:

Пусть переменная n имеет область N (натуральные числа). Чтобы доказать первое утверждение, достаточно доказать два утверждения:
(4)
(5)
Первое из этих утверждений называется базисом индукции, второе - индукционным шагом. Для доказательства второго утверждения берут произвольное натуральное число, обозначают его какой-либо буквой, скажем k, и доказывают импликацию:
U(k) ® U(k+1) (6)
Как следует из определения квантора общности, доказав это получим (5). Для доказательства (6) предполагают, что истинна посылка:
U(k) (7)
и выводят из этого предположения, что истинно ее заключение U(k+1). Утверждение (7) называется предположением индукции.
При доказательстве утверждения (2) базисом индукции является утверждение U(a), индукционным шагом – ("nіa)(U(n)®U(n+1)), предположением индукции – утверждение U(k), где k – произвольное натуральное число большее или равное a.
При доказательстве утверждения (3) базисом индукции является утверждение U(a), индукционным шагом – утверждение ("n:aЈn<b)(U(n)®U(n+1)), предположением индукции U(k), где k – произвольное натуральное число такое, что aЈn<b. Такая индукция называется индукцией по интервалу. От индукции по интервалу можно перейти к индукции спуска. Индукцией спуска называется индукция, базисом которой является утверждение U(b), индукционным шагом – утверждение ("n:aЈn<b)(U(n+1)®U(n)). Предположением индукции в этой форме является утверждение U(k+1), где k – произвольное натуральное число такое, что aЈn<b.
Иногда утверждение 1 удобно доказывать возвратной индукцией. Возвратная индукция - это индукция с базисом U(1), но с индукционным шагом ("n)("mЈn)(U(m) ® U(n)). Предположением индукции является ("m<k)U(m), где k – произвольное натуральное число. Возвратная индукция с измененным базисом и индукционным шагом применяется и при доказательстве утверждений 2 и 3.
Для доказательства утверждений 1-3 часто бывает удобной индукция с двойным базисом, то есть для случая 1 индукция с базисом U(1)ЩU(2) и индукционным шагом ("n) ((U(n)ЩU(n+1))®U(n+2)). Иногда удобно применять индукцию с тройным, четырехкратным и т.д. базисом.
Для доказательства утверждений вида
(8)
применяется индукция по двум переменным. Однако, утверждение (8) часто удается свести к индукции по одной переменной. Для этого формируем в качестве значения переменной m произвольное число и обозначаем его а. Докажем утверждение ("n)U(a,n). Из этого утверждения очевидно следует (8). Но последнее утверждение имеет вид 1 и его можно доказать индукцией. При такой схеме n называется индукционной переменной. Говорят также, что (8) доказывается по n при фиксированном m.
![]()
3.1.1
Практические
задания
1.Требуется найти ошибку в доказательстве того, что натуральные числа равны между собой.
Пусть A переменная с областью определения R(N) (множества натуральных чисел), n – переменная с областью определения N (натуральные числа). Обозначим через U(A, n) высказывание: «Если множество A содержит n элементов, то в A нет двух неравных натуральных чисел». Очевидно, утверждение
![]()
равносильно утверждению задачи.
Докажем утверждение (1) индукцией по n, причем индукцию будем применять в ее простейшей форме. Базисом индукции является:
("A)U(A,1). (2)
Докажем (2). Возьмем произвольное MМN и докажем
U(M,1). (3)
Тем самым будет доказано утверждение (2). Но на основе определения U, (3) утверждает: «Если множество M содержит один элемент, то в M нет двух неравных натуральных чисел», что очевидно. Предположим теперь в качестве предположения индукции, что ("A)U(A,n) верно для некоторого натурального k, то есть, что верно
("A)U(A,k) (4)
и докажем, что верно
("A)U(A,k+1) (5)
Тем самым утверждение (1) будет доказано. Для доказательства (5) возьмем произвольное MНN и докажем
U(M,k+1) (6)
Тем самым (5) будет доказано. На основе определения U, (6) есть утверждение: «Если множество M содержит k+1 элементов, то в M нет двух неравных натуральных чисел». Чтобы доказать эту импликацию, предположим, что ее посылка верна. Пронумеруем как-нибудь элементы множества M. Пусть, например:
![]()
Докажем, что в множестве M нет двух неравных натуральных чисел. Тем самым доказательство будет закончено. Рассмотрим два вспомогательных множества:
![]()
Каждое из них получено выбрасыванием из M одного элемента и, следовательно, содержит k элементов. В силу предположения индукции (4) U(K,k) – «Если множество K содержит k элементов, то в K нет двух неравных натуральных чисел». Но множество K как раз содержит k элементов, следовательно, в нем нет двух неравных натуральных чисел. Отсюда:
(7)
Используем еще раз предположение индукции (4). Возьмем теперь в качестве значения A множество L. Теперь из (4) получим утверждение U(L,k), что означает: «Если множество L содержит k элементов, то в нем нет двух неравных натуральных чисел». Но множество L содержит как раз k элементов, следовательно, в нем нет двух неравных натуральных чисел. В частности:
(8)
Из (7) и (8) следует, что в M нет двух неравных натуральных чисел. Доказательство закончено.
3.2 Рекурсия
Особое место для систем функционального программирования приобретает рекурсия, поскольку она позволяет учитывать значения функции на предыдущих шагах.
С теоретической точки зрения рекурсивные определения являются теоретической основой всей современной теории вычислимых функций. Рассмотрим два способа вычисления f(1)+f(2)+…+f(n). При итерации сделаем следующим образом. Определим подпрограмму:
Sub Add(S,k,f)
S=S+f
k=k-1
End Sub
Тогда процедуру без использования цикла можно определить следующим образом:
S=0
k=n
I: Add(S,k,f(k))
J: If k№0 Then Goto I
Здесь подпрограмма Add выполняется n раз последовательно и независимо, причем каждый раз используется только одна команда возврата. Это итерация.
Для рекурсии построим функцию:
If k=0 Then
Sum(f,k)=0
Else
Sum(f,k)=f(k)+Sum(f,k-1)
End If
Теперь достаточно просто узнать значение Sum(f,n). Рассмотрим частный случай при n=2. Из определения следует, что необходимо вычислить f(2), а затем обратиться к вычислению Sum(f,1), результат вычисления которого должен быть прибавлен к f(2). Следовательно, сохранить в памяти f(2), установить еще один возврат и обратиться еще один раз к нашему определению. Теперь вычисляем f(1), снова запоминаем результат в памяти, устанавливаем третий возврат и в третий раз обращаемся к определению для вычисления Sum(f,0). Последняя функция равна 0, и мы выходим из определения, используя возврат, установленный перед обращением к определению. Далее прибавляем 0 к f(1), снова выходим из определения, используя второй возврат, прибавляем 0+f(1) к f(2) и производим окончательный выход. Это рекурсия. Определение Sum использовалось не последовательно и независимо, а с вложением последующего использования в предыдущее (что характерно для индуктивного вывода), три команды возврата одновременно хранились в памяти и использовались по принципу «последний пришел – выполнился первый» (LIFO).
Здесь мы рассмотрели пример простой рекурсии. Другим более сложным примером рекурсии является вычисление чисел Фибоначчи. Их можно определить с помощью следующих формул:
![]()
Формально число Фибоначчи можно вычислить по следующей явной формуле:
F(n) = [(1 + Ц5)n – (1 - Ц5)n] / (2n Ц5).
Эта формула относительно сложна. На самом деле в этом виде задача даже полностью не решена, поскольку алгоритм использования формулы требуется уточнить. Например, осуществлять ли раскрытие внутренних скобок по формуле бинома? Какое значение брать для числа Ц5, то есть сколько брать десятичных знаков? Очевидно, что хотя результат должен быть целым, он не будет таковым. Следовательно, встает вопрос, до какого соседнего целого нужно округлять? Как быть при этом уверенным в результате?
Для этой задачи можно использовать решение с непосредственной подстановкой:
Sub F(n)
If n > 2 Then
F(n) = F(n – 1) + F(n – 2)
Else
F(n) = 1
End If
End Sub
Для приведенных выше функций существуют алгебраические выражения, по которым их можно вычислить. Поэтому, используемые для них рекурсии, будем называть простыми. Однако, существуют функции, которые не являются простыми рекурсиями. Эти функции можно определить рекурсивно, но нельзя записать в терминах алгебраических выражений. Характерным примером является функция Аккермана. Пытаясь определить эту функцию алгебраически, получим только последовательность экспонент, записанных через многоточие. С другой стороны существует простая запись этой функции через рекурсию:
A(m,n)=iif(m=0,n+1,iif(n=0,A(m-1,1),A(m-1,A(m,n-1)))).
Вообще говоря, вычисление таких функций может быть бесконечным (характерная особенность индуктивного вывода). В качестве примера приведем функцию f(m,n), результатом которой является 1 в случае, если в десятичной записи