Реферат: Логическое и функциональное программирование

Rst.Delete adAffectCurrent

Rst.Update

Rst.Close

2. Математические основы

Математическими основами индуктивного и дедуктивного вывода являются математическая логика и ее развитие логика предикатов первого порядка.

Логика используется для того, чтобы доказывать правильность или неправильность тех или иных утверждений или высказываний. Это имеет большое значение при решении задач проектирования и для других вычислительных задач. Так искусственный интеллект во многом опирается на гипотезу символьных систем. Упрощенно эта гипотеза утверждает, что, организовав огромную структуру взаимосвязанных символов, представляющих реальные знания и сложный набор символьных процессов, позволяющий оперировать структурами с целью создания новых структур, можно создать машину, работающую также хорошо в смысле интеллектуальной деятельности, как человек.

2.1 Алгебра высказываний

Одним из основных понятий логики является понятие высказывания, правильность или неправильность которого мы стараемся определить. Попытаемся определить смысл этого термина. Высказыванием называют предложения, про которые разумно говорить, разумно считать, что они являются истинными или ложными. Неуточненность понятий «истинно» и «ложно» делают понятие высказывания расплывчатым. Однако, вводя ограничения можно это понятие уточнить. Фразы «Пойдем в кино?», «Да здравствует президент!» не являются высказываниями (как и любые вопросительные и восклицательные предложения). Фраза «Треугольник называется равносторонним, если все его стороны равны» (как и любое другое определение) также не является высказыванием. Фразы «2*2 = 4» и «3>5» - высказывания (первое истинное, второе ложное). Фраза «В повести “Шинель” 200755 букв» - высказывание, но нам неизвестна его истинность. Фразу «Эта книга хорошая» не следует относить к высказываниям в традиционной логике в силу неопределенности понятия «хороший».

Поэтому, определим, как простое высказывание – высказывание, для которого в определенных условиях времени и места можно делать вывод об его истинности или ложности, причем это высказывание задается простым предложением («Сегодня идет дождь»).

Из простых высказываний с помощью связок можно строить сложные высказывания, и тогда возникает задача определения их истинности в зависимости от истинности простых высказываний, его составляющих.

Переменную, в область значений которой входят только высказывания (а точнее истинностные значения T, F) будем называть высказывательной переменной (двоичной или булевой). В силу определения областью значений этих переменных является двоичный алфавит.

Функции от любого конечного числа двоичных переменных, также способные принимать лишь два значения T и F,принято называть булевыми функциями. Иногда такие функции называют переключательными, так как реализующие такие функции схемы осуществляют переключение входных каналов, подавая на них сигналы, то одного, то другого вида.

Областью определения булевых функций от n – переменных служит совокупность всевозможных n – мерных упорядоченных наборов (векторов размерностью n), компонентами которых являются буквы двоичного алфавита T и F.

Для любого n = 1, 2, . . . среди n – мерных наборов можно ввести естественную лексикографическую упорядоченность. Для этого поставим в соответствие с F – 0, а с T – 1. Тогда набор преобразуется в последовательность 0 и 1. Такой набор уже можно рассматривать как представление целого неотрицательного числа в двоичной системе счисления. Например, TTTF® 1110 ® 14. Это число будем называть номером набора. Эти наборы называются также кортежами или, используя геометрическую терминологию, точками.

Последнее название связано с тем, что имеется естественная возможность отождествлять различные n – мерные наборы с вершинами n-мерного куба.

Естественную упорядоченность наборов мы получим, если расположим их в порядке возрастания номеров. Первым в таком расположении является нулевой набор, все компоненты которого 0, последним – набор, все компоненты которого 1.

Отсюда, наборы размерности n нумеруются числами от 0 до 2^{n -1} . А отсюда в частности вытекает:

1. Имеется в точности 2ⁿ двоичных n-мерных наборов.

Нетрудно также подсчитать число различных булевых функций от n переменных. Для каждого набора значений, независимо от значений других наборов, можно выбрать в качестве значений функции T или F. Следовательно, прибавление каждого нового набора к области определения булевой функции увеличивает число различных булевых функций ровно в два раза.

На одном наборе можно определить две различных булевых функции. На двух – 2² и т. д. Продолжая подобным образом и с учетом 1, получим:

2. Имеется точно различных булевых функций от n переменных.

Следует отметить, что здесь и далее к числу функций от n переменных относятся и такие функции f(x1, x2, . . ., xn), которые не зависят от тех или иных переменных xi. В частности, в числе функций окажутся функции – константы (тождественная истина и тождественная ложь), которые можно рассматривать как функции от нуля переменных.

Условимся называть невырожденными функциями от n переменных такие функции, которые существенно зависят от всех этих переменных. Функции же от n переменных, сводящиеся к функциям от меньшего числа переменных называются вырожденными.

В теории булевых функций особое значение имеют функции одной и двух переменных. Имеется всего = 4 разных функций одной переменной.

x f	G1	G2	G3	G4
0	0	0	1	1
1	0	1	0	1

G1, G4 – константы 0 и 1.

G2 = x.

и называется функцией отрицания или инверсии.

Число булевых функций от двух переменных равно . Выпишем сводную таблицу всех этих функций.

x	y	F1	F2	F3	F4	F5	F6	F7	F8	F9	F10	F11	F12	F13	F14	F15	F16
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

Из выписанных функций шесть будут вырожденными, а именно функции F1, F4, F6, F11, F13, F16. Действительно, легко видеть: