Днф и сднф в чем разница

ДНФ, СДНФ, КНФ, СКНФ

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

Конъюнкцией n переменных f (x₁, x₂, …, x_n) = x₁ x₂…x_n называется функция, которая принимает значение 1, если и только если все переменные равны 1 (и, значит, равна 0, если хотя бы одна из этих переменных равна 0).

Дизъюнкцией n переменных f (x₁, x₂, …, x_n) = x_1Ú x_2Ú … Ú x_n называется такая функция, которая равна 0 если и только если все переменные равны 0 (и, значит, равна 1 тогда и только тогда, когда хотя бы одна переменная равна 1).

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

Будем обозначать через (x₁, x₂, … , x_n) новую функцию, которая на наборе переменных x₁, x₂, …, x_n принимает значение, противоположное f(x₁, x₂, …, x_n).

Заметим, что в перечисленных далее свойствах в роли x, y, z может выступать любая логическая функция. Все свойства легко могут быть доказаны из приведенных выше определений этих функций.

1. Универсальные границы:

x1 = 1; x0 = х; х1 = х; х0 = 0.

2. Ассоциативность конъюнкции и дизъюнкции:

x(yz) = (xy)z; x (y z) = (x y) z.

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

3. Поглощение (“целое поглощает часть”):

х ху = х(1 у) = х.

4. Два распределительных закона:

х (y z) = x y  x z; х (y z) = (x y)(x z),

оба свойства могут быть доказаны простым рассуждением (например, если х = 0, тогда по свойству 1 справа выражение равно 0 и слева тоже 0, если х = 1, то справа стоит y z и слева будет то же самое).

5. Правила де Моргана:

оба эти правила обобщаются на любое число переменных:

6. Правило Блейка:

Пусть К₁ и К₂ – какие-то логические функции, тогда

что легко доказывается справа налево:

Следствием правила Блейка являются два правила обобщенного поглощения:

Заметим, что правила Блейка и следствия из него часто используются для упрощения дизъюнкции (см. разд. 5)

Замечание. Конъюнкция, дизъюнкция, отрицание были определены для объектов, принимающих лишь два значения 0 и 1. Однако бывают случаи, когда можно ввести такие операции для некоторых других объектов (эти операции также называют иногда конъюнкцией, дизъюнкцией и отрицанием), для которых также выполнены свойства 1–6. В этом случае говорят, что на этих объектах введена булева алгебра.

Например, пусть – некоторое множество точек (или элементарных событий в теории вероятности),  – множество подмножеств из  . Если A, B принадлежат  , то можно ввести сумму множеств (дизъюнкцию) A+B = AB (равную объединению точек из А и В), произведение множеств (конъюнкцию) АВ = А В (равное набору точек, входящих и в А, и в B одновременно) и дополнение (отрицание А), т. е. – множество точек из  , не входящих в А. Тогда для этих операций (и это легко проверить) будут выполнены свойства 1–6. Таким образом, множество всех подмножеств из  является булевой алгеброй.

3. ДНФ, СДНФ, КНФ, СКНФ

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

Например, является простой конъюнкцией,

Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция простых конъюнкций.

Например, выражение является ДНФ.

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

Например, выражение является ДНФ, но не СДНФ. Выражение является СДНФ.

Аналогичные определения (с заменой конъюнкции на дизъюнкцию и наоборот) верны для КНФ и СКНФ. Приведем точные формулировки.

Простой дизъюнкцией называется дизъюнкция одной или нескольких переменных, при этом каждая переменная входит не более одного раза (либо сама, либо ее отрицание).Например, выражение – простая дизъюнкция,

Конъюнктивной нормальной формой (КНФ) называется конъюнкция простых дизъюнкций (например выражение – КНФ).

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

Например, выражение является СКНФ.

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

а) переход от ДНФ к КНФ

Алгоритм этого перехода следующий: ставим над ДНФ два отрицания и с помощью правил де Моргана (не трогая верхнее отрицание) приводим отрицание ДНФ снова к ДНФ. При этом приходится раскрывать скобки с использованием правила поглощения (или правила Блейка). Отрицание (верхнее) полученной ДНФ (снова по правилу де Моргана) сразу дает нам КНФ:

Заметим, что КНФ можно получить и из первоначального выражения, если вынести у за скобки;

б) переход от КНФ к ДНФ

Этот переход осуществляется простым раскрытием скобок (при этом опять-таки используется правило поглощения)

Таким образом, получили ДНФ.

Обратный переход (от СДНФ к ДНФ) связан с проблемой минимизации ДНФ. Подробнее об этом будет рассказано в разд. 5, здесь же мы покажем, как упростить ДНФ (или СДНФ) по правилу Блейка. Такая ДНФ называется сокращенной ДНФ;

в) сокращение ДНФ (или СДНФ) по правилу Блейка

Применение этого правила состоит из двух частей:

— если среди дизъюнктных слагаемых в ДНФ имеются слагаемые , то ко всей дизъюнкции добавляем слагаемое К₁К₂. Проделываем эту операцию несколько раз (можно последовательно, можно одновременно) для всех возможных пар слагаемых, а затем, применяем обычное поглощение;

— если добавляемое слагаемое уже содержалось в ДНФ, то его можно отбросить совсем, например,

Разумеется, сокращенная ДНФ не определяется единственным образом, но все они содержат одинаковое число букв (например, имеется ДНФ , после применения к ней правила Блейка можно прийти к ДНФ, равносильной данной):

в) переход от ДНФ к СДНФ

Если в какой-то простой конъюнкции недостает переменной, например, z, вставляем в нее выражение ,после чего раскрываем скобки (при этом повторяющиеся дизъюнктные слагаемые не пишем). Например:

г) переход от КНФ к СКНФ

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

Таким образом, из КНФ получена СКНФ.

Заметим, что минимальную или сокращенную КНФ обычно получают из соответствующей ДНФ.

Днф и сднф в чем разница

Приведем к ДНФ формулу :
Выразим логические операции → и ↓ через :

• в ней нет одинаковых элементарных конъюнкций
• в каждой конъюнкции нет одинаковых пропозициональных букв
• каждая элементарная конъюнкция содержит каждую пропозициональную букву из входящих в данную ДНФ пропозициональных букв, причём в одинаковом порядке.

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

• 
• 
• 

в этом случае будет представлен без инверсии: по закону идемпотентности). Например:

Научный форум dxdy

В чем назначение ДНФ, СДНФ, КНФ, СКНФ: зачем и почему?

Последний раз редактировалось ariel777 04.11.2020, 08:25, всего редактировалось 1 раз.

Я не знаю применений нормальных форм — хотя может быть, что они есть.

Можно сформулировать так: любой раздел математики занимается постановкой естественных и интересных вопросов и поиском ответов на эти вопросы.
Какие вопросы естественные и интересные, а какие нет — в этом состоит математическая культура, сложившаяся за века.

Когда математики ставят такой вопрос, они чаще всего не задумываются о его возможных применениях. Просто — если мы в какой-то момент ввели операции конъюнкции и дизъюнкции, а затем с их помощью научились строить произвольные булевы формулы, то невозможно не задать себе вопрос: а может быть, любые такие формулы можно упростить, привести к какому-то простому виду? И как он может выглядеть?

Уже потом зачастую оказывается, что ответы на естественные и интересные вопросы где-то нужны. Может быть, в других математических дисциплинах, может в приложениях к реальному миру. Сотни лет назад математики пытались вывести формулу корней кубического уравнения в первую очередь не потому, что это было где-то позарез нужно, а из интереса — вот есть формула для линейных уравнений, есть для квадратных, а какая будет для кубических? В этот момент они не думали, что эти размышления приведут к появлению идеи комплексных чисел, а от них (через кватернионы) — и к идее векторов; без обеих этих идей немыслима вся современная физика. Когда математики развивали теорию чисел, они не думали, что она пригодится в криптографии. Таких примеров множество.

Теперь — почему изучение этой темы включено в учебный курс.
1) Курс составлялся носителем этой самой математической культуры. Поэтому, с его точки зрения, без данной темы курс выглядел бы как-то убого и незавершённо;
2) Одна из целей этого курса и любых других математических курсов — привить учащимся (может быть, не всем) эту самую математическую культуру. Показать, какие вопросы естественные и интересные, чтобы новое поколение учёных тоже в будущем ставило такие вопросы и искало на них ответы, не обязательно задумываясь о практической пользе.
3) Для разной аудитории, однако, требуются разные учебные курсы. Не уверен, что условных «гуманитариев» (равно как и «технарей», во всяком случае большинство из них) педагогически оправдано заставлять учить эти формы. А если человеку самому интересна мат.логика, то наверное он и не будет задавать такой вопрос.

Последний раз редактировалось Sender 04.11.2020, 13:24, всего редактировалось 3 раз(а).

В действительности тот же самый вопрос можно поставить о любой области математики. В том числе и школьной, «элементарной».
Меня как-то спрашивала одна коллега (дама «старой закалки», старше меня): для чего нужны логарифмы? Мне, мол, они никогда в жизни не понадобились, для чего я их учила? Помню ещё вопрос студентки, озлобившейся на математику: зачем мне нужна теорема Пифагора? Что она вообще даёт в жизни? Вопрос был поставлен именно так. Наверно, с подобными вопросами встречались все, кто когда-либо преподавал математику.
Думаю, эти вопросы не бессмысленны. Действительно ли нужно учить математике всех? Или не нужно?
По сути, трудный вопрос. Дать на него исчерпывающий ответ вряд ли возможно.
Иногда я рассказываю в ответ притчу о Евклиде и ленивом юноше, что пришёл учиться математике у мудреца. Иногда вспоминаю афоризмы вроде «Математика — гимнастика ума» или «Математику затем учить надо, что она ум в порядок приводит». Но сам-то я при этом ни в чём не уверен. Потому как прекрасно помню: когда-то и меня — студента — заставляли учить историю КПСС, политэкономию и т.п. «хотя бы для того, чтобы вы были грамотными» — так нам говорили. Подобную формулу я всегда считал издательством над здравым смыслом. Уверен: если бы я никогда не учил историю КПСС, то отрицательных эмоций в моей жизни было бы поменьше А грамотности, уверен и в этом, не поубавилось бы. Вот я и думаю: возможно, у кого-то математика вызывает те же самые эмоции, что у меня когда-то — марксистская шелуха. Поэтому какой-либо категоричной позиции я здесь не занимаю.

Хочу ещё отметить: встречаются два чётко различных уровня подобных вопросов. Первый — уровень простой риторики, когда задающий вопрос уже для себя решил, что математика ему не нужна. А сам вопрос «зачем мне это?» — лишь форма протеста. В этом случае я стараюсь не спорить. Второй уровень — уровень пытливого ученика. Когда человек не прочь потрудиться, но хочет заранее хотя бы приблизительно знать — а что на выходе? Что он будет делать конкретно вот с этим знанием? Такая постановка вопроса, по-моему, заслуживает уважения. И на такие вопросы я стараюсь отвечать серьёзно. Если могу хоть что-то сказать.

Последний раз редактировалось ariel777 04.11.2020, 13:14, всего редактировалось 2 раз(а).

Последний раз редактировалось bot 04.11.2020, 13:25, всего редактировалось 3 раз(а).

А кто знат? Вообще, вопрос из программы без предъявления её содержания нахожу слабо осмысленным.
Впрочем, уверен, что программа по логике для гуманитариев носит чисто ознакомительный характер и уж точно не идёт дальше этих нормальных форм. Оказывается, даже такие сверх-поверхностные сведения, кого-то напрягают.
Если же в курс включить мотивацию, да с приложениями, то придётся добавлять часы и .
напряжённых станет больше.

— Ср ноя 04, 2020 16:16:48 —

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

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

Функции тождественны, если $f(x_1, x_2, \dots, x_n)=g(x_1, x_2, \dots, x_n)$ на всех наборах аргументов (таблицы истинности совпадают).

$f(\overline,\overline,\dots,\overline)=\overline$ => $g$ двойственна $f$ ($f$ и $g$ можно поменять местами, то есть функции $f$ и $g$ двойственны друг другу). Из простейших функций двойственны друг другу константы 0 и 1, а из законов де Моргана следует двойственность конъюнкции и дизъюнкции. Тождественная функция, как и функция отрицания, двойственна сама себе (самодвойственная функция).

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

Нормальные и совершенные нормальные формы: КНФ, ДНФ, СДНФ, СКНФ

Простая конъюнкция или конъюнкт = конъюнкция некоторого конечного набора переменных или их отрицаний, причём каждая переменная встречается не более одного раза.

Дизъюнктивная нормальная форма (ДНФ) = дизъюнкция простых конъюнкций. Пример: $a \overline c\lor b c\lor\overline$.

Совершенная ДНФ (СДНФ) относительно некоторого набора переменных = ДНФ, у которой в каждую конъюнкцию входят все переменные данного набора, причём в одном и том же порядке. Пример: $a \overline c\lor a b c\lor\overline b\overline$.

СДНФ и СКНФ можно построить по таблице истинности.

Булева Алгебра (Алгебра Буля)

Формально: непустое множество $A$ с двумя бинарными операциями $\land$ (конъюнкция), $\lor$ (дизъюнкция), унарной операцией $\lnot$ (отрицание) и двумя выделенными элементами: 0 (или Ложь) и 1 (или Истина) такими, что для всех »a», »b» и »c» из множества $A$ верны следующие аксиомы:

Проблема разрешимости

Все формулы алгебры логики делятся на тождественно истинные (всегда 1), тождественно ложные (всегда 0) и выполнимые (иногда 0, иногда 1).

Проблема разрешимости: к какому классу (из вышеперечисленных) относится данная формула?

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

Нетабличный способ определения формулы к данному классу

Способ состоит в приведении формулы к нормальной форме (ДНФ или КНФ) и использовании правил, которые позволяют определить, какой является формула (тождественно истинной, тождественно ложной, выполнимой).

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

Замкнутые классы. Монотонные функции

Замкнутый класс — такое множество булевых функций, замыкание которого относительно операции суперпозиции совпадает с ним самим: $[P]=P$. Другими словами, любая функция, которую можно выразить формулой с использованием функций множества $P$, снова входит в это же множество.

В 1941 году Эмиль Пост представил полное описание системы замкнутых классов (решетку Поста).

Примеры замкнутых классов:

Множество $P_2$ всех возможных булевых функций замкнуто.

Особо важны для теории булевых функций следующие замкнутые классы, называемые предполными классами:

• Класс $T_0$ функций, сохраняющих 0: $T_0=\left\$.
• Класс $T_1$ сохраняющих 1: $T_1=\left\$.
• $S$ самодвойственных функций: $S=\left\,\dots,\overline)=\overline\right\>$.
• $M$ монотонных функций: $M=\left\$.
• $L$ линейных функций: $L=\left\\right\>$.

Ни один из предполных классов не содержится целиком в объединении четырёх остальных; любой замкнутый класс булевых функций, отличный от $P_2$, целиком содержится хотя бы в одном из пяти предполных классов.

Другими важными замкнутыми классами являются:

• Класс конъюнкций K, являющийся замыканием множества $\<\land,0,1\>$. Он представляет собой множество функций вида $c_0\land(c_1\lor x_1)\land\ldots\land(c_n\lor x_n)$.
• Класс дизъюнкций D, являющийся замыканием множества $\<\lor,0,1\>$. Он представляет собой множество функций вида $c_0\lor(c_1\land x_1)\lor\ldots\lor(c_n\land x_n)$.
• Класс функций одной переменной U, содержащий только константы, отрицание и селектор (функцию, равную одному из своих аргументов на всех наборах их значений).
• Класс $O^m$ функций (m — любое натуральное, большее единицы число), удовлетворяющих следующему условию: для любых m наборов, на которых функция принимает нулевое значение, найдется переменная, также принимающая нулевое значение на всех этих наборах.
• Класс $O^\infty$ функций, для которых выполнено условие $f(x_1,\ldots,x_n)\ge x_i$, где $x_i$ — одна из переменных функции.
• Класс $I^m$ функций (m — любое натуральное, большее единицы число), удовлетворяющих следующему условию: для любых m наборов, на которых функция принимает единичное значение, найдется переменная, также принимающая единичное значение на всех этих наборах.
• Класс $I^\infty$ функций, для которых выполнено условие $f(x_1,\ldots,x_n)\le x_i$, где $x_i$ — одна из переменных функции.

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

Полные системы функций. Базисы + Пост — основная теорема о функциональной полноте

Множество функций $A$ — полная система, если замыкание $A$ совпадает с множеством всех булевых функций $[A]=P_2$ (т.е. любую логическую функцию можно выразить формулой с использованием только функций множества $A$).

Критерий Поста формулирует необходимое и достаточное условие полноты системы булевых функций:
Система булевых функций полна тогда и только тогда, когда она не содержится целиком ни в одном из классов $T_0$, $T_1$, $S$, $M$, $L$. В частности, если функция не входит ни в один из классов Поста, она сама по себе формирует полную систему. В качестве примера можно назвать штрих Шеффера (отрицание конъюнкции).

Широко известны такие полные системы булевых функций:

• $\left\<\land,\lor,\neg\right\>$ (конъюнкция, дизъюнкция, отрицание) — ДНФ.
• $\left\<\land,\oplus,1\right\>$ (конъюнкция, сложение по модулю 2, константа 1) — полином Жегалкина.

Полная система функций называется базисом, если она перестаёт быть полной при исключении из неё любого элемента. Первая из упоминавшихся выше полных систем базисом не является, поскольку согласно законам де Моргана либо дизъюнкцию, либо конъюнкцию можно исключить из системы и восстановить с помощью остальных двух функций. Вторая система является базисом — все три её элемента необходимы для полноты.
Максимально возможное число булевых функций в базисе — 4.

Иногда говорят о системе функций, полной в некотором замкнутом классе, и соответственно о базисе этого класса. Например, систему $\left\<\oplus,1\right\>$ можно назвать базисом класса линейных функций.

Алгебра Жегалкина

Полином Жегалкина — полином над $Z_2$ (коэффициенты только 0 и 1), в качестве произведения — конъюнкция, а в качестве сложения — исключающее или (xor, не равно, сложение по модулю 2). Общий вид:

$P = a \oplus \bigoplus_< \begin 1\leq i_1< \ldots<i_k\leq n \\ k\in\overline <0,n>\end >a_\land x_\land\ldots \land x_, \quad a, a_\in \<0,1\>.$

По теореме Жегалкина каждая булева функция единственным образом представляется в виде полинома Жегалкина.

Переключательные схемы

Функции проводимости $F$ некоторых переключательных схем:

a)

Схема не содержит переключателей и проводит ток всегда, следовательно $F=1$;

б) Схема содержит один постоянно разомкнутый контакт, следовательно $F=0$;
в) Схема проводит ток, когда переключатель х замкнут, и не проводит, когда х разомкнут, следовательно, $F(x) = x$;
г) — Схема проводит ток, когда переключатель х разомкнут, и не проводит, когда $х$ замкнут, следовательно, $F(x) = \bar x$;
д) Схема проводит ток, когда оба переключателя замкнуты, следовательно, $F(x) = x \land y$;
е) Схема проводит ток, когда хотя бы один из переключателей замкнут, следовательно, $F(x)=x \lor y$;
ж) Схема состоит из двух параллельных ветвей и описывается функцией .

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

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

Способы доказательства тавтологии и следствия

Тавтологией называется тождественно истинное высказывание, верное при любых значениях своих компонентов. Формула в исчислении высказываний является тавтологией или тождественно истинной, если её значение для любых значений аргументов истинно.

Примеры тавтологий:

• $ A \to A $ («Из »A» следует »A»»)
• $(A) \lor (\lnot A)$ («»A» или не-»A»»)
• $\overline

  $.

• $(P \land (P \to Q)) \to Q$
• $A \to (B \to A)$

Формула F называется тавтологией, или тождественно истинной формулой, если F истинно при любой интерпретации.

Понятие тавтологии "двойственно"’ понятию выполнимой формулы: $F$ – тавтология тогда и только тогда, когда $\lnot F$ не выполнима. Определение эквивалентных формул, данное выше, может быть переформулировано следующим образом: F эквивалентна G, если F є G – тавтология.

Формула является »тождественно истинной», если она истинна при любых значениях входящих в неё переменных. Вот несколько широко известных примеров тождественно истинных формул логики высказываний:

Законы де Моргана:

1) $ \neg (p \lor q) \leftrightarrow (\neg p \land \neg q)$;

2) $ \neg (p \land q) \leftrightarrow (\neg p \lor \neg q)$;

Закон контрапозиции:

$(p\to q)\leftrightarrow(\neg q\to \neg p)$;

1) $p\lor(p\land q)\leftrightarrow p$;

2) $p\land(p\lor q)\leftrightarrow p$;

1) $p\land(q\lor r)\leftrightarrow(p\land q)\lor(p \land r)$;

2) $p\lor(q\land r)\leftrightarrow(p\lor q)\land(p \lor r)$.

Общие свойства символа тавтология

Правило введения и удаления логических знаков

Метод Резолюции. Теорема о замене. Теорема о резолюциях. Доказательство тавтологии с помощью метода резолюции

Правило резолюций – это правило вывода, восходящее к методу доказательства теорем через поиск противоречий; используется в логике высказываний и логике предикатов первого порядка. Правило резолюций, применяемое последовательно для списка резольвент, позволяет ответить на вопрос, существует ли в исходном множестве логических выражений противоречие

Пусть $C_1$ и $C_2$ — два предложения в исчислении высказываний, и пусть $C_1 = P \lor C’_1$, а $C_2 = \lnot P \lor C’_2$, где $P$ — пропозициональная переменная, а $C’_1$ и $C’_2$ — любые предложения (в частности, может быть, пустые или состоящие только из одного литерала). Правило вывода

называется правилом резолюции. Предложения C₁ и C₂ называются »резольвируемыми» (или »родительскими»), предложение $C’_1 \lor C’_2$ — »резольвентой», а формулы $P$ и $\lnot P$ — »контрарными» литералами.

Алгоритм:

1. Составляем список дизъюнктов.
2. Находим среди них какую-либо пару, в которой один дизъюнкт содержит переменную, а другой — ее отрицание. На основе этих двух дизънктов получаем один новый, которы заносим в список. И начинаем поиск подходящей пары снова.
3. Все это продолжается до тех пор, пока на некотором шаге в списке не окажется пара $a$ и $\lnot a$.

Исчисление высказываний

Составное высказывание

Сокращенные таблицы истинности

Выбираем значение переменной, подставляем в логическое выражение, упрощаем выражение, заполняем строки в таблице истинности. Повторяем этот шаг пока таблица истинности не будет заполнена.

Формальные теории (исчисление)

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

Формальная теория – это совокупность абстрактных объектов, не связанных с реальным миром, в котором представлены правила оперирования множеством символов в строго синтаксической трактовке без учета их смыслового содержания, т.е. семантики.

Формальная теория считается определенной, если:

• Задано конечное или счётное множество произвольных символов. Конечные последовательности символов называются выражениями теории.
• Имеется подмножество выражений, называемых формулами.
• Выделено подмножество формул, называемых аксиомами.
• Имеется конечное множество отношений между формулами, называемых правилами вывода.

Аксиоматичное построение исчисления высказываний, правило вывода (правило заключения)

• алфавит есть множество символов:
  • $а, b, . а_1, b_1. $ — (пропозициональные) переменные, значением которой может быть логическое высказывание;
  • $\neg, \land, \lor, \to$ (отрицание, конъюнкция, дизъюнкция и импликация) — пропозициональные связк;
  • (,) — скобки, служебные символы;
  • Если $P$ — пропозициональная переменная, то $P$ — формула.
  • Если $A$ — формула, то $\neg A$ — формула.
  • Если $A$ и $B$ — формулы, то $A \to B$, $A \land B$ и $A \lor B$ — формулы.
  • Других соглашений нет.
  1. $A \to (B \to A)$;
  2. $((A \to (B \to C)) \to ((A \to B) \to (A \to C)))$;
  3. $A \land B \to A$;
  4. $A \land B \to B$;
  5. $A \to (B \to (A \land B))$;
  6. $A \to (A \lor B)$;
  7. $B \to (A \lor B)$;
  8. $(A \to C) \to ((B \to C) \to ((A \lor B) \to C))$;
  9. $\neg A \to (A \to B)$;
  10. $(A \to B) \to ((A \to \neg B)\to \neg A)$;
  11. $A\lor\neg A$.

  вместе с единственным правилом вывода:

  $\frac$ (»Modus ponens» — правило заключений) — если $A$ и $A \to B$ — выводимые формулы, то $B$ также выводима.

  Сравнение результатов аксиоматической теории исчисления с результатами, относящимися к тавтологии

  Предикаты. n-местный предикат. Кванторы

  Предикат (»n»-местный, или »n»-арный) — функция с множеством значений $\< 0,1 \>$ (или «ложь» и «истина»), определённая на множестве $M=<_<1>>\times <_<2>>\times \ldots \times <_>$. Таким образом, каждый набор элементов множества »M» он характеризует либо как «истинный», либо как «ложный».

  Тождественно-истинный предикат: $P\left ( x_1, . x_n \right) \equiv 1$ (на любом наборе аргументов равен 1).

  Тождественно-ложный предикат: $P\left ( x_1, . x_n \right) \equiv 0$ (на любом наборе аргументов равен 0).

  Предикат выполнимый, если хотя бы на одном наборе аргументов он равен 1.

  Квантор — общее название для логических операций, ограничивающих область истинности какого-либо предиката. Чаще всего используются:

  • Квантор всеобщности $\forall$ — «для всех…», «для каждого…» или «каждый…», «любой…», «для любого…»).
  • Квантор существования $\exists$, читается: «существует…» или «найдётся…».

  В математической логике приписывание квантора к формуле называется связыванием или навешиванием квантора.

  Связанные переменные

  Переменная $v$ связана в формуле $F$, если $F$ содержит $Kv$, где $K$ — квантор.

  Предикаты на конечных областях. Логика одноместных предикатов

  Значений $x$ конечное число, их можно перебрать.

  Конъюнкция — пересечение областей определения, дизъюнкция — объединение областей определения, отрицание — дополнение области определения.

  Кванторы по предикатным переменным

  Правило отрицания кванторов: применяется для построения отрицаний высказываний, содержащих кванторы, и имеет вид:

  Похожие публикации:

  1. В какой строке допущена ошибка
  2. Как защитить код c
  3. Как поменять обои на рабочем столе windows 8
  4. Что такое события и с чем они связаны в 1с