Совершенные нормальные формыФормула F называется СОВЕРШЕННОЙ КОНЪЮНКТИВНОЙ НОРМАЛЬНОЙ ФОРМОЙ (СКНФ) от высказывательных переменных системы (1) x 1,…, x n, если она является конъюнкцией различных полных элементарных дизъюнкций от этих переменных (при этом равенство дизъюнкций понимается с точностью до порядка членов). Формула F называется СОВЕРШЕННОЙ ДИЗЪЮНКТИВНОЙ НОРМАЛЬНОЙ ФОРМОЙ (СДНФ) от высказывательных переменных системы (1) x 1,…, x n, если она является дизъюнкцией различных полных элементарных конъюнкций от этих переменных. Или иначе: если двойственная ей формула F* является СКНФ. Из замечания 2 следует, что СДНФ не может быть тождественно ложным высказыванием. Пусть некоторая функция f трёх переменных задана следующей таблицей истинности:
1) Выбираем наборы значений переменных, для которых (0; 1; 1), (1; 0; 1), (1; 1; 0), (1; 1; 1). 2) Каждому из этих наборов сопоставляем (ставим в соответствие) конъюнкцию переменных набору (0; 1; 1) – конъюнкцию набору (1; 0; 1) – конъюнкцию набору (1; 1; 0) – конъюнкцию набору (1; 1; 1) – конъюнкцию 3) Дизъюнкция этих конъюнкций равна единице в тех и только тех случаях, когда и заданная функция принимает значение 1 и, следовательно, представляет собой одно из возможных выражений этой функции, т.е.
Это выражение является, очевидно, СДНФ данной функции. 15)
16) предикат – это то, что утверждается о субъекте. Например, в высказывании “7 - простое число”, “7” – субъект, “простое число” – предикат. Это высказывание утверждает, что “7” обладает свойством “быть простым числом”. Одноместным предикатом Р(x) называется произвольная функция переменного x, определенная на множестве M и принимающая значение из множества {1; 0}. Множество М, на котором определен предикат Р(x), называется областью определения предиката Р(x). Множество всех элементов Конъюнкцией двух предикатов P(x) и Q(x) называется новый (сложный) предикат Очевидно, что областью истинности предиката
17) Термом называется символьное выражение: t(X1, X2, …, Xn), где t — имя терма, называемая функтор или «функциональная буква», а X1, X2, …, Xn — термы, структурированные или простейшие. термы – это алгебраические выражения, определяющие функции, значения которых вычисляются с помощью операций Например, если Р(х) и Q(x,y) – одноместный и двухместный предикаты, а q, r – переменные высказывания, то формулами будут, например, слова (выражения): Не является формулой, например, слово: Из определения формулы логики предикатов ясно, что всякая формула алгебры высказываний является формулой логики предикатов.
18)
Высказывания можно считать предикатами, не содержащими переменных, т. е. 0-местными предикатами
Связывание кванторами переменных в предикате дает истинное или ложное высказывание. 19) Синтаксис и семантика логики предикатов. В определениях формальных языков, таких, как логические языки или языки программирования, выделяют два основных аспекта: синтаксис и семантику. синтаксис логики предикатов включают в себя символы (имена) предикатов из некоторого Множества, символы (имена) функций из некоторого множества, символы (имена) констант из некоторого множества C={ c1, c2,... }, логические связки, кванторы всеобщности и существования и вспомогательные символы (скобки, запятые). 20)
21) О логическом значении формулы логики предикатов можно говорить лишь тогда, когда задано множество M, на котором определены входящие в эту формулу предикаты. Логическое значение формулы логики предикатов зависит от значений трех видов переменных: 1) значений входящих в формулу переменных высказываний, 2) значений свободных предметных переменных из множества М, 3) значений предикатных переменных. При конкретных значениях каждого из трех видов переменных формула логики предикатов становится высказыванием, имеющим истинное или ложное значение. В качестве примера рассмотрим формулу В формулу (1) входит переменный предикат P(x,y), предметные переменные x,y,z, две из которых y и z – связанные кванторами, а x – свободная. Возьмем за конкретное значение предиката P(x,y) фиксированный предикат P0(x,y): “x<y”, а свободной переменной х придадим значение 22) Равносильные формулы логики предикатов. Две формулы логики предикатов А и В называются равносильными, если они равносильны на всякой области. Ясно, что все равносильности алгебры высказываний будут верны, если в них вместо переменных высказываний подставить формулы логики предикатов. Ясно, что все равносильности алгебры высказываний будут верны, если в них вместо переменных высказываний подставить формулы логики предикатов.
23) Общезначимость и выполнимость формул логики предикатов. Формула А логики предикатов называется выполнимой, если существует область, на которой эта формула выполнима. Формула А логики предикатов называется общезначимой, если она тождественна истинна на всякой области (на любой модели). 1. Если формула А общезначима, то она и выполнима на всякой области (модели). 2. Если формула А тождественно истинна в области М, то она и выполнима в этой области. 3. Если формула А тождественно ложна в области М, то она не выполнима в этой области. 4. Если формула А не выполнима, то она тождественно ложна на всякой области (на всякой модели). 5. Для того, чтобы формула А логики предикатов была общезначима, необходимо и достаточно, чтобы ее отрицание было не выполнимо. 6. Для того, чтобы формула А логики предикатов была выполнимой, необходимо и достаточно, чтобы формула
25) логическое следование. Принцип дедукции. Логическое следование – это отношение, существующее между посылками и обоснованно выводимыми из них заключениями. Логическое следование относится к числу фундаментальных, исходных понятий логики, которую нередко характеризуют как науку о том, "что из чего следует".
26) понятие аксиоматических систем. "Аксиоматическая система" или коротко "аксиоматика" - система логических рассуждений, в которой есть аксиомы и правила вывода, и все утверждения выводятся строго на основе этих аксиом и правил, не прибегая к дополнительным средствам.
27) полные логические системы, в которых получить "новое" знание в силу их полноты невозможно
28)
30) Темпоральная логика (англ. temporal logic) в логике — это логика, учитывающая причинно-следственные связи в условиях времени. Используется для описания последовательностей явлений и их взаимосвязи по временной шкале. Значение утверждений меняется со временем. Рассмотрим утверждение: "Я голоден". Темпоральная логика позволяет выразить утверждения типа "Я всегда голоден", "Я иногда голоден" или "Я голоден, пока я не поем" В качестве логических операторов обычно используются (
31) нечеткие множества описываются функциями принадлежности. функция принадлежности элемента к множеству может принимать любые значения в интервале [0...1], а не только 0 или 1. 32) модальная логика.- логика, в которой используют модальные операторы.
Возможно, что Москва столица России. Не верно, что не Москва столица России.
33) Алгоритм - это определенная последовательность логических действий для решения поставленной задачи. Каждый алгоритм предполагает существование начальных (входящих) данных и в результате работы приводит к получению определенного результата. Работа каждого алгоритма происходит путем выполнения последовательности некоторых элементарных действий. Эти действия называют шагами, а процесс их выполнения называют алгоритмическим процессом. Таким образом проявляется свойство дискретности алгоритма Важным свойством алгоритмов является массовость, или возможность применения к различным входным данным. То есть, каждый алгоритм призван решать класс однотипных задач. Необходимым условием, которому удовлетворяет алгоритм, является детерминированность, или определенность. Это означает, что выполнение команд алгоритма происходит по единому образцу и приводит к одинаковому результату для одинаковых входных данных. Входные данные алгоритма могут быть ограничены набором допустимых входных данных. Применение алгоритма к недопустимым входным данным может приводить к тому, что алгоритм никогда не остановится или попадет в тупиковое состояние (зависание), из которого не сможет выйти.
34) Подлежащую проверке программу неоднократно запускают с теми входными данными, относительно которых результат известен заранее. Затем сравнивают полученный машиной результат с ожидаемым. 35) Основная идея, лежащая в основе машины Тьюринга, очень проста. Машина Тьюринга — это абстрактная машина (автомат), работающая с лентой отдельных ячеек, в которых записаны символы. Машина также имеет головку для записи и чтения символов из ячеек, которая может двигаться вдоль ленты. На каждом шагу машина считывает символ из ячейки, на которую указывает головка, и, на основе считанного символа и внутреннего состояния, делает следующий шаг. При этом, машина может изменить свое состояние, записать другой символ в ячейку или передвинуть головку на одну ячейку вправо или влево. На основе исследования этих машин был выдвинут тезис Тьюринга (основная гипотеза алгоритмов): Некоторый алгоритм для нахождения значений функции, заданной в некотором алфавите, существует тогда и только тогда, когда функция исчисляется по Тьюрингу, то есть когда ее можно вычислить на машине Тьюринга. Этот тезис является аксиgомой, постулатом, и не может быть доказан математическими методами, поскольку алгоритм не является точным математическим понятиям. 37) Рекурсивная функция. С каждым алгоритмом можно сопоставить функцию, которую он вычисляет. Однако возникает вопрос, можно ли произвольной функции сопоставить машину Тьюринга, а если нет, то для каких функций существует алгоритм? Исследования этих вопросов привели к созданию в 1930-х годах теории рекурсивных функций. Класс вычисляемых функций был записан в образ, напоминающий построение некоторой аксиоматической теории на базе системы аксиом. Сначала были выбраны простейшие функции, вычисление которых очевидно. Затем были сформулированы правила (операторы) построения новых функций на основе уже существующих. Необходимый класс функций состоит из всех функций, которые можно получить из простейших применением операторов. Подобно тезису Тьюринга в теории вычислительных функций была выдвинута гипотеза, которая называется тезис Чёрча: Числовая функция тогда и только тогда алгоритмически исчисляется, когда она частично рекурсивна. Доказательство того, что класс вычисляемых функций совпадает с исчисляемыми по Тьюрингу, происходит в два шага: сначала доказывают вычисление простейших функций на машине Тьюринга, а затем — вычисление функций, полученных в результате применения операторов. Таким образом, неформально алгоритм можно определить как четкую систему инструкций, определяющих дискретный детерминированный процесс, который ведет от начальных данных (на входе) к искомому результату (на выходе), если он существует, за конечное число шагов; если искомого результата не существует, алгоритм или никогда не завершает работу, либо заходит в тупик. 39) классом P (от англ. polynomial) называют множество задач, для которых существуют «быстрые» алгоритмы решения классом NP называют множество задач распознавания, решение которых при наличии некоторых дополнительных сведений можно «быстро» проверить на машине Тьюринга. действительно ли решение задачи легче проверить, нежели отыскать? Например, верно ли, что среди чисел {−2, −3, 15, 14, 7, −10, …} есть такие, что их сумма равна 0 (задача о суммах подмножеств)? Ответ да, потому что −2 −3 + 15 −10 = 0 легко проверяется несколькими сложениями (информация, необходимая для проверки положительного ответа, называется сертификатом). Следует ли отсюда, что так же легко подобрать эти числа? Проверить сертификат так же легко, как найти его? Кажется, что подобрать числа сложнее (не доказано). 38) Тезис Черча- все алгоритмические системы эквивалентны, потому что делают один и тот же результат. В разных разделах математики встречаются алгоритмически неразрешимые задачи, т.е. задачи, для которых нет алгоритма решения, причём нет не потому что его пока не придумали, а потому что он невозможен в принципе. Разумеется, алгоритм надо понимать в смысле машин Тьюринга и рекурсивных функций.
|
:
или их отрицаний, принимающую при этих значениях переменных значение 1:
,
,
,
.
.
, при которых предикат принимает значения “истина” (1), называется множеством (областью) истинности предиката Р(x)
, который принимает значение “истина” при тех и только тех значениях 
.
, так как формулу 
переменная х входит связанно, а в формулу Р(х) переменная х входит свободно.
Для всякого х Р(х) истинно… 
называют квантором всеобщности
Существует x, при котором P(x) истинно.” Символ 
называют квантором существования.
, (1) в которой двухместный предикат Р(x, y) определен на множестве MхM, где M={0,1,2,…,n,…}, т.е. MхM=NхN.
. Тогда при значениях y, меньших x0=5, предикат P0(x0,y) принимает значение “ложь”, а импликация 
при всех 
принимает значение “истина”, т.е. высказывание 
имеет значение “истина”.
была не общезначима.
)
-верно,что
- возможно,что
