Совершенные нормальные формы.

Формула F называется СОВЕРШЕННОЙ КОНЪЮНКТИВНОЙ НОРМАЛЬНОЙ ФОРМОЙ (СКНФ) от высказывательных переменных системы (1) x₁,…,x_n, если она является конъюнкцией различных полных элементарных дизъюнкций от этих переменных (при этом равенство дизъюнкций понимается с точностью до порядка членов).

Формула F называется СОВЕРШЕННОЙ ДИЗЪЮНКТИВНОЙ НОРМАЛЬНОЙ ФОРМОЙ (СДНФ) от высказывательных переменных системы (1) x₁,…,x_n, если она является дизъюнкцией различных полных элементарных конъюнкций от этих переменных.

Или иначе: если двойственная ей формула F^* является СКНФ. Из замечания 2 следует, что СДНФ не может быть тождественно ложным высказыванием.

Пусть некоторая функция f трёх переменных задана следующей таблицей истинности:

1) Выбираем наборы значений переменных, для которых :

(0; 1; 1), (1; 0; 1), (1; 1; 0), (1; 1; 1).

2) Каждому из этих наборов сопоставляем (ставим в соответствие) конъюнкцию переменных или их отрицаний, принимающую при этих значениях переменных значение 1:

набору (0; 1; 1) – конъюнкцию ,

набору (1; 0; 1) – конъюнкцию ,

набору (1; 1; 0) – конъюнкцию ,

набору (1; 1; 1) – конъюнкцию .

3) Дизъюнкция этих конъюнкций равна единице в тех и только тех случаях, когда и заданная функция принимает значение 1 и, следовательно, представляет собой одно из возможных выражений этой функции, т.е.

.

Это выражение является, очевидно, СДНФ данной функции.

15) Математические теории в качестве примеров интерпретации алгебры Буля.

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

Формальная теория — множество, правильно постоенных формул или выражений, определяющих язык теорий.

Подмножество формул множества ППФ

правило вывода, то есть, конечное множество отношений между формулами

Ф1,Ф2,...,Фn

Ф3=f (Ф1,Ф2)

теоремой называется такая формула Ф, что существует доказательство:

Ф1...Фn

Фn=Ф

Аксиоматическая теорема(теория) полна, если присоединение к её аксиомам формулы, не являющейся теоремой(теорией) делает теорию противоречивой.

Интерпретация формальной теории в /.../ содержат теорию, называемую исчислением высказываний — пример формальной теории имеет:

а) множество ППФ

б) множество аксиом

в) правила вывода

1) Ф (А)/Ф (В)

2) (Ф,Ф->В)/В

16) предикат – это то, что утверждается о субъекте.

Например, в высказывании “7 - простое число”, “7” – субъект, “простое число” – предикат. Это высказывание утверждает, что “7” обладает свойством “быть простым числом”.

Одноместным предикатом Р(x) называется произвольная функция переменного x, определенная на множестве M и принимающая значение из множества {1; 0}.

Множество М, на котором определен предикат Р(x), называется областью определения предиката Р(x).

Множество всех элементов , при которых предикат принимает значения “истина” (1), называется множеством (областью) истинности предиката Р(x)

Конъюнкцией двух предикатов P(x) и Q(x) называется новый (сложный) предикат , который принимает значение “истина” при тех и только тех значениях , при которых каждый из предикатов принимает значение “истина”, и принимает значение “ложь” во всех остальных случаях.

Очевидно, что областью истинности предиката является общая часть области истинности предикатов P(x) и Q(x), т.е. пересечение .

17) Термом называется символьное выражение: t(X1, X2, … , Xn), где t — имя терма, называемая функтор или «функциональная буква», а X1, X2, … , Xn — термы, структурированные или простейшие. термы – это алгебраические выражения, определяющие функции, значения которых вычисляются с помощью операций

Например, если Р(х) и Q(x,y) – одноместный и двухместный предикаты, а q, r – переменные высказывания, то формулами будут, например, слова (выражения):

Не является формулой, например, слово: , так как формулу переменная х входит связанно, а в формулу Р(х) переменная х входит свободно.

Из определения формулы логики предикатов ясно, что всякая формула алгебры высказываний является формулой логики предикатов.

18) Для всякого х Р(х) истинно… называют квантором всеобщности

Существует x, при котором P(x) истинно.” Символ называют квантором существования.

Высказывания можно считать предикатами, не содержащими переменных, т. е. 0-местными предикатами

Связывание кванторами переменных в предикате дает истинное или ложное высказывание.

19) Синтаксис и семантика логики предикатов.

В определениях формальных языков, таких, как логические языки или языки программирования, выделяют два основных аспекта: синтаксис и семантику.

синтаксис логики предикатов включают в себя символы (имена) предикатов из некоторого Множества , символы (имена) функций из некоторого множества , символы (имена) констант из некоторого множества C={ c1, c2, ... }, логические связки , кванторы всеобщности и существования и вспомогательные символы (скобки, запятые).

20) Теория множеств и её связь с алгеброй Буля.

Алгебра множеств является подразделом булевых алгебр, впервые возникших в трудах Дж.Буля (1815–1864). В аксиомах булевой алгебры отражена аналогия между понятиями «множества», «событие» и «высказывания». Логические высказывания можно записать с помощью множеств и проанализировать с помощью булевой алгебры.

21) О логическом значении формулы логики предикатов можно говорить лишь тогда, когда задано множество M, на котором определены входящие в эту формулу предикаты. Логическое значение формулы логики предикатов зависит от значений трех видов переменных: 1) значений входящих в формулу переменных высказываний, 2) значений свободных предметных переменных из множества М, 3) значений предикатных переменных.

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

В качестве примера рассмотрим формулу , (1) в которой двухместный предикат Р(x, y) определен на множестве MхM, где M={0,1,2,…,n,…}, т.е. MхM=NхN.

В формулу (1) входит переменный предикат P(x,y), предметные переменные x,y,z, две из которых y и z – связанные кванторами, а x – свободная.

Возьмем за конкретное значение предиката P(x,y) фиксированный предикат P⁰(x,y): “x<y”, а свободной переменной х придадим значение . Тогда при значениях y, меньших x⁰=5, предикат P⁰(x⁰,y) принимает значение “ложь”, а импликация при всех принимает значение “истина”, т.е. высказывание имеет значение “истина”.

22) Равносильные формулы логики предикатов.

Две формулы логики предикатов А и В называются равносильными, если они равносильны на всякой области. Ясно, что все равносильности алгебры высказываний будут верны, если в них вместо переменных высказываний подставить формулы логики предикатов. Ясно, что все равносильности алгебры высказываний будут верны, если в них вместо переменных высказываний подставить формулы логики предикатов.

23) Общезначимость и выполнимость формул логики предикатов.

Формула А логики предикатов называется выполнимой, если существует область, на которой эта формула выполнима.

Формула А логики предикатов называется общезначимой, если она тождественна истинна на всякой области (на любой модели).

1. Если формула А общезначима, то она и выполнима на всякой области (модели).

2. Если формула А тождественно истинна в области М, то она и выполнима в этой области .

3. Если формула А тождественно ложна в области М , то она не выполнима в этой области .

4. Если формула А не выполнима, то она тождественно ложна на всякой области (на всякой модели).

5. Для того, чтобы формула А логики предикатов была общезначима, необходимо и достаточно, чтобы ее отрицание было не выполнимо.

6. Для того, чтобы формула А логики предикатов была выполнимой, необходимо и достаточно, чтобы формула была не общезначима.

24) Метод резолюций в логике предикатов.

B A₁ … A_n

Метод резолюции основан на использовании правил резолюции. В общем виде правила резолюции позволяет из 2-х следующих предложений

1) B₁ …B_m A₁…Aj A_n

2) B₁….B_j … B_r A₁ … A_n

Для некоторых существует согласующая подстановка такая, что выполняется условие:

Aj _j (выполнение перехода)

Вывести третье предложение

Разложение: B₁ ,B_m , B₁ , , B ’ , B ’ A , A , A , A , A ’ , …A ’

B+A A … A | B’ A A ’…A

B A1’ Ak’ A2

С помощью правила резолюции, то есть значение переменной при которой из математического приложения SU(c ) вывести пустое разложение.

Основные названия областей языка программирования, пролог

Constans, domains, data base (предиката динамической базы данных), predicate (описание имён и структур определённого пользования), goal(цель, которая описывает желаемый результат), clauses(клауза)

25) логическое следование. Принцип дедукции.

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

26) понятие аксиоматических систем.

"Аксиоматическая система" или коротко "аксиоматика" - система логических рассуждений, в которой есть аксиомы и правила вывода, и все утверждения выводятся строго на основе этих аксиом и правил, не прибегая к дополнительным средствам.

27) полные логические системы, в которых получить "новое" знание в силу их полноты невозможно

28) Клазуальная форма. Принцип логического программирования.

Преобразование предложений из стандартной формы в клазуальную

Любое предложение в стандартной форме можно перевести. Причём результатом множества клаус совместно, если только совместно исходное множество. Для упрощённой записи формулы, надо опускать внешние скобки.

Для преобразований форм из стандартного в клазуальную использую следующие системы правил эквивалентности:

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

Для снижения шагов при преобразовании надо в процессе преобразования не заменять импликации, для этого полезны следующие эквивалентности.

Полезные эквивалентности:

29) Клазуальная логика.

Clause (от анг. Предложение) – предложение общего вида: В₁, В₂, … В_m А₁ , … A_m

Где В₁, … В_m ;А₁ , … A_m атомарные формы при этом n m . Совместно А₁ , … A_m называются совместные посылки.

В₁, … В_m - альтернативные заключения

A₁ & A₂& … A_n B₁ + B₂ + … B_m

Таким образом (,) в посылке clause означают конъюнктивные связки между предложениями, в В₁…В_m (альтернативам заключений, означают дизъюнктивные связи).

Множество clause невыполнимы, если из него можно вывести пустое предложение.

А1 –принятие решения

30) Темпоральная логика(англ. temporal logic) в логике — это логика, учитывающая причинно-следственные связи в условиях времени. Используется для описания последовательностей явлений и их взаимосвязи по временной шкале.

Значение утверждений меняется со временем.

Рассмотрим утверждение: "Я голоден". Темпоральная логика позволяет выразить утверждения типа "Я всегда голоден", "Я иногда голоден" или "Я голоден, пока я не поем"

В качестве логических операторов обычно используются ( )

31) нечеткие множества описываются функциями принадлежности.

функция принадлежности элемента к множеству может принимать любые значения в интервале [0...1], а не только 0 или 1.

32) модальная логика.- логика, в которой используют модальные операторы.

-верно,что

- возможно,что

Возможно, что Москва столица России. Не верно, что не Москва столица России.

33) Алгоритм - это определенная последовательность логических действий для решения поставленной задачи.

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

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

Необходимым условием, которому удовлетворяет алгоритм, является детерминированность, или определенность. Это означает, что выполнение команд алгоритма происходит по единому образцу и приводит к одинаковому результату для одинаковых входных данных.

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

34) Подлежащую проверке программу неоднократно запускают с теми входными данными, относительно которых результат известен заранее. Затем сравнивают полученный машиной результат с ожидаемым.

35) Основная идея, лежащая в основе машины Тьюринга, очень проста. Машина Тьюринга — это абстрактная машина (автомат), работающая с лентой отдельных ячеек, в которых записаны символы. Машина также имеет головку для записи и чтения символов из ячеек, которая может двигаться вдоль ленты. На каждом шагу машина считывает символ из ячейки, на которую указывает головка, и, на основе считанного символа и внутреннего состояния, делает следующий шаг. При этом, машина может изменить свое состояние, записать другой символ в ячейку или передвинуть головку на одну ячейку вправо или влево.

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

Этот тезис является аксиgомой, постулатом, и не может быть доказан математическими методами, поскольку алгоритм не является точным математическим понятиям.\ Характерно:

- бесконечна память

- есть головка, видящая только 1 ячейку

- движется на один шаг

- может перезаписать или не перезаписывать элемент.

36)варианты машины Тьюринга.

есть детерминированые а есть недетерминированые

Детерминированная машина Тьюринга имеет функцию перехода, которая по комбинации текущего состояния и символа на ленте определяет три вещи: символ, который будет записан на ленте, направление смещения головки по ленте и новое состояние конечного автомата. Например, X на ленте в состоянии 3 однозначно определяет переход в состояние 4, запись на ленту символа Y и перемещение головки на одну позицию влево.

В случае недетерминированной машины Тьюринга, комбинация текущего состояния автомата и символа на ленте может допускать несколько переходов. Например, X на ленте и состояние 3 допускает как состояние 4 с записью на ленту символа Y и смещением головки вправо, так и состояние 5 с записью на ленту символа Z и смещением головки влево.

Как НМТ «узнаёт», какой из возможных путей приведёт в допускающее состояние? Есть два способа это представить.

§ Можно считать, что НМТ — «чрезвычайно удачлива»; то есть всегда выбирает переход, который в конечном счете приводит к допускающему состоянию, если такой переход вообще есть.

§ Можно представить, что в случае неоднозначности перехода (текущая комбинация состояния и символа на ленте допускает несколько переходов) НМТ делится на копии, каждая из которых следует за одним из возможных переходов.

То есть в отличие от ДМТ, которая имеет единственный «путь вычислений», НМТ имеет «дерево вычислений» (в общем случае — экспоненциальное число путей). Говорят, что НМТ допускает входные данные, если какая-нибудь ветвь этого дерева останавливается в допускающем состоянии, иначе НМТ входные данные не допускает. (Таким образом, ответы «ДА» и «НЕТ» в случае недетерминированных вычислений несимметричны.)

37) Рекурсивная функция. С каждым алгоритмом можно сопоставить функцию, которую он вычисляет. Однако возникает вопрос, можно ли произвольной функции сопоставить машину Тьюринга, а если нет, то для каких функций существует алгоритм? Исследования этих вопросов привели к созданию в 1930-х годах теории рекурсивных функций. Класс вычисляемых функций был записан в образ, напоминающий построение некоторой аксиоматической теории на базе системы аксиом. Сначала были выбраны простейшие функции, вычисление которых очевидно. Затем были сформулированы правила (операторы) построения новых функций на основе уже существующих. Необходимый класс функций состоит из всех функций, которые можно получить из простейших применением операторов.

Подобно тезису Тьюринга в теории вычислительных функций была выдвинута гипотеза, которая называется тезис Чёрча: Числовая функция тогда и только тогда алгоритмически исчисляется, когда она частично рекурсивна.

Доказательство того, что класс вычисляемых функций совпадает с исчисляемыми по Тьюрингу, происходит в два шага: сначала доказывают вычисление простейших функций на машине Тьюринга, а затем — вычисление функций, полученных в результате применения операторов.

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

39) классом P (от англ. polynomial) называют множество задач, для которых существуют «быстрые» алгоритмы решения

классом NP называют множество задач распознавания, решение которых при наличии некоторых дополнительных сведений можно «быстро» проверить на машине Тьюринга.

действительно ли решение задачи легче проверить, нежели отыскать?

Например, верно ли, что среди чисел {−2, −3, 15, 14, 7, −10, …} есть такие, что их сумма равна 0 (задача о суммах подмножеств)? Ответ да, потому что −2 −3 + 15 −10 = 0 легко проверяется несколькими сложениями (информация, необходимая для проверки положительного ответа, называется сертификатом). Следует ли отсюда, что так же легко подобрать эти числа? Проверить сертификат так же легко, как найти его? Кажется, что подобрать числа сложнее (не доказано).

38) Тезис Черча- все алгоритмические системы эквивалентны, потому что делают один и тот же результат.

В разных разделах математики встречаются алгоритмически неразрешимые задачи, т.е. задачи, для которых нет алгоритма решения, причём нет не потому что его пока не придумали, а потому что он невозможен в принципе. Разумеется, алгоритм надо понимать в смысле машин Тьюринга и рекурсивных функций.