Высказывания реферат по логике

Обновлено: 05.07.2024

бесконечно много, и в этом ее отличие от большинства других наук.

Однородные законы объединяются в логические системы, которые тоже

Без логического закона нельзя понять то, что такое логическое следование

и что такое доказательство. Правильное, или, как обычно говорят, логичное,

мышление – это мышление по законам логики, по тем абстрактным схемам,

которые фиксируются ими. Законы логики составляют тот невидимый

каркас, на котором держится последовательное рассуждение и без которого

Среди множества логических законов логика выделяет четыре основных,

выражающих коренные свойства логического мышления – его

определенность, непротиворечивость, последовательность и обоснованность.

Это законы тождества, противоречия, исключенного третьего и

достаточного основания. Они действуют в любом рассуждении, в какой бы

логической форме оно ни протекало и какую бы логическую операцию ни

Цель моего реферата рассмотреть основные законы классической

Любая мысль в процессе рассуждения должна иметь определенное,

устойчивое содержание. Это коренное свойство мышления – его

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

всех логических законов. Он говорит: если утверждение истинно, то оно

т. п. Чистое утверждение тождества кажется настолько бессодержательным,

Всякая мысль в процессе рассуждения должна быть тождественна самой

себе ( а есть а , или а=а , где под а понимается любая мысль). Закон тождества

может быть выражен формулой р → р (если р , то р ), где р – лю бое

Закон тождества утверждает, что любая мысль (любое рассуждение)

обязательно должна быть равна (тождественна) самой себе, т. е. она должна

быть ясной, точной, простой, определенной. Говоря иначе, этот закон

запрещает путать и подменять понятия в рассуждении (т. е. употреблять одно

и то же слово в разных значениях или вкладывать одно и то же значение в

разные слова), создавать двусмысленность, уклоняться от темы и т п. D

Из закона тождества следует: нельзя отождествлять различные мысли,

нельзя тождественные мысли принимать за нетождественные. Нарушение

этого требования в процессе рассуждения нередко бывает связано с

различным выражением одной и той же мысли в языке. Например, два

выражают одну и ту же мысль (если, разумеется, речь идет об одном и том

же лице). Предикаты этих суждений – равнозначные понятия: кража и есть

тайное хищение чужого имущества. Поэтому было бы ошибочным

С другой стороны, употребление многозначных слов может привести к

ошибочному отождествлению различных мыслей. Например, в уголовном

Уголовным кодексом, в гражданском праве этим словом обозначают меру

административного воздействия. Очевидно, употреблять подобное слово в

Когда закон тождества нарушается непроизвольно, по незнанию, тогда

возникают просто логические ошибки; но когда этот закон нарушается

преднамеренно, с целью запутать собеседника и доказать ему какую-нибудь

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

образом,D софизм D— это внешне правильное доказательство ложной мысли с

помощью преднамеренного нарушения логических законов.

Из бесконечного множества логических законов самым популярным

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

объявлен наиболее важным принципом не только человеческого мышления,

Закон противоречия говорит о противоречащих друг другу

высказываниях, т. е. о таких высказываниях, одно из которых является

отрицанием другого. К ним относятся, например, высказывания «Луна —

высказываний что-то утверждается, в другом — это же самое отрицается.

Если обозначить буквой а произвольное высказывание, то выражение не-

Идея, выражаемая законом противоречия, кажется простой и даже

банальной:D высказывание и его отрицание не могут быть вместе

Этот закон формулируется следующим образом : неверно, что а и не-а (не

могут быть истинными две мысли , одна из которых отрицает другую).

Неверно, например, что трава зеленая и не зеленая, что Луна спутник Земли и

не спутник Земли и т.д. Закон выражается формулой ┐ ( р ^ р ) (неверно, что р

и не–р одновременно истинны). Под р понимается любое высказывание, под

^ р – отрицание высказывания р , знак ┐ перед всей формулой – отрицание

Закон противоречия говорит о противоречащих высказываниях — отсюда

его название. Но он отрицает противоречие, объявляет его ошибкой и тем

самым требует непротиворечивости — отсюда другое распространенное имя

DПротиворечия бываютD контактными , когда одно и то же утверждается и

сразу же отрицается (последующая фраза отрицает предыдущую в речи, или

последующее предложение отрицает предыдущее в тексте) и дистантными ,

когда между противоречащими друг другу суждениями находится

значительный интервал в речи или в тексте. Например, в начале своего

выступления лектор может выдвинуть одну идею, а в конце высказать мысль,

противоречащую ей; так же и в книге в одном параграфе может утверждаться

то, что отрицается в другом. Понятно, что контактные противоречия, будучи

слишком заметными, почти не встречаются в мышлении и речи. Иначе

обстоит дело с дистантными противоречиями: будучи неочевидными и не

очень заметными, они часто проходят мимо зрительного или мысленного

взора, непроизвольно пропускаются, и поэтому их часто можно встретить в

интеллектуально-речевой практике. Так, Bитaлий Ивaнoвич Свинцов

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

несколько страниц сначала утверждалось: «В первый период творчества

начала своего творчества Маяковский обладал качествами, которые

Противоречия также бывают явными и неявными. В первом случае одна

мысль непосредственно противоречит другой, а во втором случае

противоречие вытекает из контекста: оно не сформулировано, но

подразумевается. Например, в учебнике «Концепции современного

Эйнштейна, следует, что, по современным научным представлениям,

пространство, время и материя не существуют друг без друга: без одного нет

Система исчисления высказываний может быть построена методом допущений. Этот метод ближе к обычным содержательно очевидным представлениям в том отношении, что доказательства в системах, построенных этим методом, почти не отличаются от математических доказательств и от рассуждений в других науках. Здесь оно излагается по книге Е. Слупецкого, Л. Борковского «Элементы математической логики и теории… Читать ещё >

Логика высказываний ( реферат , курсовая , диплом , контрольная )

Важнейшей функцией логики является установление того, что из чего следует, а значит установление того, какие формулы являются теоремами, а какие нет. Это достигается с помощью аксиоматического метода. При аксиоматическом построении исчисления высказываний выбирают некоторое, небольшое количество формул, которые включают в систему без доказательства. Это аксиомы системы. Остальные формулы могут быть присоединены к системе только тогда, когда они следуют из аксиом или являются определениями. Существует много эквивалентных систем исчисления высказываний, различающихся аксиомами и исходными терминами. Здесь мы опишем систему Д. Гильберта и В. Аккермана. В исчислении высказываний определение формулы такое же, как и в алгебре высказываний.

В качестве аксиом принимаются следующие четыре высказывания:

В этой системе принимаются три определения:

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

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

Из двух формул? и? >? получаем новую формулу ?.

Из сформулированных правил и аксиом можно вывести новые правила вывода формул.

ПРАВИЛО I. Если? ? — доказуемая формула, то доказуема также формула ?.

Доказательство: Подставим в ?) формулу ?. Получим? ?> ?. Поскольку? ? доказуемая формула, то, по правилу ?) доказуема и формула ?.

ПРАВИЛО II. Если? — доказуемая формула, а? — любая другая формула, то формула? ? является также доказуемой.

Доказательство: Подставим в в) вместо р формулу ?, а вместо q — формулу ?. Получаем? ? ?. Схема заключения дает? ?.

ПРАВИЛО III. Если? ? — доказуемая формула, то доказуема и формула? ?.

Доказательство: Получаем из с) заменой р на ?, q на? и применяем схемы заключения.

ПРАВИЛО IV. Если ?>? доказуемая формула, то формула ??>? ? также доказуема.

Доказательство: Получаем из ?) заменой р на ?, q на ?, r на? и применяем схемы заключения.

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

Докажем, например, формулу:

Доказательство: Заменим в d) r наr. Получаем (p>q)> ((rp)>(rq)), но по Д1 эта формула есть иная запись доказываемой формулы.

Доказательство: Подставим в формулу вместо р формулу ?, вместо q формулу ?, вместо r формулу ?. Получаем: (? > ?)>((?> ?)>(?> ?)) .

Применяя два раза схему заключения, получаем: ?> ?.

Легко доказать, что в предложенной аксиоматической системе выводимы формулы алгебры высказываний. Докажем например, что формула рp выводима.

Доказательство: Подставляем в в) вместо q переменную р, получаем формулу р> рp. Из а) той же подстановкой получаем рp> р. По правилу У выводим формулу p> р. По Д1 эта формула представляет собой иную запись формулырp.

Аналогичным образом можно доказать остальные формулы алгебры высказываний.

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

Правило отделения (обозначает ПО):

Правило введения конъюнкции ВК ?

Способ чтения этой схемы аналогичен.

Правило удаления конъюнкции:

Правило УК можно записать в виде одной схемы:

Правило введения дизъюнкции:

Правило удаления дизъюнкции:

Правило введения эквивалентности:

6)Правило удаления эквивалентности:

1. В первых n-1 строках выписываются последовательно выражения ?₁, ?₂,… ?_п-1 в качестве условий теоремы.

2. К доказательству можно присоединить:

ранее доказанные теоремы в качестве новых строк;

новые строки на основании уже имеющихся строк по правилам ПО, ВК, УК, ВД, УД, ВЭ, УЭ.

Доказательство закончено, если его последняя строка есть выражение ?_п. Последняя строка доказательства не нумеруется; тем самым отмечается, что доказательство закончено.

Косвенное доказательство выражения ?₁ >(?₂>(?₃> …(?_п-1 >?_п)…) строится следующим образом:

а) В первых n-1 строках выписываются последовательно выражения ?₁, ?₂,… ?_п-1 в качестве условий теоремы.

В n-ой строке выписывается выражение?_п в качестве допущения косвенного доказательства.

К доказательству можно присоединить:

ранее доказанные теоремы в качестве новых строк;

новые строки на основании уже имеющихся строк по правилам ПО, ВК, УК, ВД, УД, ВЭ, УЭ.

Продемонстрируем приемы доказательства на ряде примеров. Их мы будем нумеровать с указанием слева Т_і (теорема номер і)

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

Рубрика	Философия
Вид	реферат
Язык	русский
Дата добавления	29.11.2016
Размер файла	36,7 K

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ЮРИДИЧЕСКИЙ ФАКУЛЬТЕТ

ТЕМА: «КЛАССИЧЕСКАЯ ЛОГИКА ВЫСКАЗЫВАНИЙ"

Павлюкевич В.И.

1. Язык и семантика КЛВ

2. Основные законы КЛВ

3. Логические отношения между формулами КЛВ

4. Основные способы умозаключений КЛВ

Список использованных источников

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

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

Этим занимались многие мыслители, но как стройная научная теория логика впервые сформировалась в IV веке до н.э. в трудах выдающегося древнегреческого философа Аристотеля (384-322 до н.э.).

Целью работы в реферате является изучение классической логики высказываний.

Для достижения поставленной цели необходимо решить следующие задачи:

1. Рассмотреть язык и семантику КЛВ.

2. Изучить основные законы КЛВ.

3. Дать характеристику логическим отношениям между формулами КЛВ.

4. Изучить основные способы умозаключений КЛВ.

В ходе изучения классической логики высказываний основным методом работы стал метод теоретического анализа литературы по этой теме.

Реферат состоит из введения, основной части, заключения, списка использованных источников (включает ____ позицию).

Общий объем реферата составляет ____ страниц.

1. Язык и семантика КЛВ

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

Несмотря на то, что отдельные фрагменты этой теории разрабатывались еще античными мыслителями, как стройная система она сложилась лишь к концу XIX в. Её аксиоматизацию впервые осуществил немецкий логик Готлоб Фреге.

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

1) пропозициональные переменные - p, q, r, s, .

2) пропозициональные связки - , &, ?, ?, ?, ?.

3) скобки - ( , ).

Значимые выражения в языке КЛВ называются формулами. Пропозициональные переменные сами по себе уже являются (атомарными) формулами. Более сложные формулы получаются из атомарных с использованием связок.

Определение формулы. (1) пропозициональные переменные являются формулами; (2) если А и В - формулы, то А, А & В, А ? В, А ? В, А ? В, А ? В - тоже формулы; (3)ничто другое не является формулой.

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

Приоритет 1 2 3 4 5 6

Упражнение. Расставьте пропущенные скобки в следующих формулах:

а) p ? q & r ? s & q ? p ? s ? q ? r

б) p & q ? r & s ? q ? p ? s ? q & r

- «Неверно, что Джульетта некрасивая

- «Если Джульетта красива, а Ромео храбр,

Семантика языка КЛВ основана на двух принципах:

1) Принцип бивалентности. Каждая пропозициональная переменная, замещающая собой простое предложение, может быть либо истинной, либо ложной. Истинность будем обозначать как 1, ложность - как 0.

2) Принцип композициональности. Истинностное значение сложной формулы есть функция от истинностных значений входящих в нее переменных.

Таким образом, каждая пропозициональная связка трактуется как истинностно-истинностная функция. Для наглядности воспользуемся таблицей:

p q p p & q p ? q p ? q p ? q p ? q

1 1 0 1 1 0 1 1

1 0 0 0 1 1 0 0

0 1 1 0 1 1 1 0

Математические аналоги логических функций:

Лог. функция символ Мат. функция символ

1 отрицание x инверсия 1 - х

2 конъюнкция x & y умножение х · у

3 дизъюнкция x ? y сложение х + у

4стр. дизъюнкция x ? y не равно х ? у

5 импликация x ? y меньше или равно х ? у

6 эквиваленция x ? y равно х = у

Алгоритм построения таблицы истинности:

1) Определить число строк (оно вычисляется по формуле k = 2n, где k - количество строк, а n - число различных пропозициональных переменных, входящих в формулу).

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

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

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

С помощью констант (связок) атомарные высказывания соединяются в более сложные высказывания. Так из двух высказываний p и q с помощью констант образуются высказывания

1) Пропозициональная переменная есть формула

3) Всякая формула есть либо пропозициональная переменная или образуется из пропозициональных переменных последовательным применением правила 2).

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

1) Опускаются скобки, объемлющие отдельные переменные.

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

2 АЛГЕБРА ВЫСКАЗЫВАНИЙ

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

2) Значение формул образованных неоднократным применением логических связок к атомарным высказываниям, задается таблицей:

р	q	`p	`q	pÙq	pÚq	p→q	p≡q
0	0	1	1	0	0	1	1
0	1	1	0	0	1	1	0
1	0	0	1	0	1	0	0
1	1	0	0	1	1	1	1

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

Так, пользуясь указанным алгоритмом можно легко вычислить истинностное значение формулы:

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

Функция исчисления высказываний выражает логический закон, если является тождественно истинной при всех возможных значениях переменных. Так, с помощью таблицы убеждаемся, что функция рÚ`p выражается логический закон: закон исключенного третьего:

р	`р	рÚ`p
0	1	1
1	0	1

Аналогичным образом убеждаемся, что функция рÙ`p тоже выражается логический закон: закон непротиворечия:

р	`p	рÙ`	рÙ`p
0	1	0	1
1	0	0	1

С помощью таблиц истинности можно убедится, что нижеприведенные функции выражают логические законы:

Закон тождества: рºр (1)

для конъюнкции: рÙ`p (2) (закон непротиворечия)

для дизъюнкции: рÚ`p (2 1 ) (закон исключенного третьего)

для конъюнкции: рÙр º р (3)

для дизъюнкции: рÚ р º р (3 1 )

для конъюнкции: рÙ q º qÙр (4)

для дизъюнкции: рÚ q º qÚр (4 1 )

для конъюнкции: (рÙq) ÙrºpÙ (qÙr ) ºpÙ qÙr (5)

для дизъюнкции: (рÚq) ÚrºpÚ (qÚr ) ºpÚ qÚr (5 1 )

для конъюнкции дизъюнкций: рÙ( q Úr) º (pÙq) Ú (рÙr ) (6)

для дизъюнкции конъюнкций: рÚ(qÙr) º (pÚ q) Ù (рÚr) (6 1 )

для конъюнкции дизъюнкций: рÙ( q Úр) ºp (7)

для дизъюнкции конъюнкций: рÚ(qÙ р) ºp (7 1 )

Закон двойственности (теорема де Моргана):

для конъюнкции: рÙqº`р Ú`q (8)

для дизъюнкции: рÚqº`р Ù`q (8 1 )

Закон двойного отрицания: `р º р (9)

3 РАВНОСИЛЬНОСТЬ ФОРМУЛ ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ. КОНЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА

Формулы φ и ψ называются равносильными, если формула φ ≡ ψ тождественно истина. Например, формула (p Ù`p) Ú q равносильна q, потому что формула (p Ù`p) Ú q ≡ q тождественно истина (проверку с помощью таблиц истинности предоставляем читателю). Формулы p Ú`p и qÚ`q также равносильны, потому что тождественно истинна формулы p Ú`p ≡ qÚ`q.

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

(р ≡ q) ≡ (р → q) Ù (q→р) (10)

(р ≡ q) ≡ (`p Ú q) Ù (`qÚр) (12)

(р ≡ q) ≡ (p Ù q) Ú (`рÙ`q) (13)

р Ùq ≡`р Ú`q (19)

р Ú q ≡`рÙ`q (20)

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

На основании установленных эквивалентностей вводим следующие правила:

а1) Со знаками Ú и Ù можно оперировать как в алгебре, пользуясь ассоциативным, коммутативным и дистрибутивным законами;

а2) `р можно заменить р;

а3) р Ùq можно заменить выражением`р Ú`q, а р Ú q - выражением`рÙ`q ;

а4) р → q можно заменить выражением `p Ú q, а р ≡ q – выражением (`p Ú q) Ù(`qÚр).

Например, привести к конъюнктивной нормальной форме формулу:

((р Ú q) Ù`q ) Ú (rÙq).

Последовательным применением правила а3) получаем :

((р Ú q) Ù`q ) Ú (rÙq) ≡((р Ú q) Ù`q ) Ù (rÙq) ≡((р Ú q) Ú`q ) Ù (`rÚ`q) ≡

Применяя к последней формуле закон дистрибутивности, получаем формулу:

(`р Ú ` q )Ù( qÙ`q) Ù (`rÚ`q).

Наконец, применяя правило а2) получаем конъюнктивную нормальную форму:

(`р Úq )Ù( qÚ`q) Ù (`rÚ`q).

Очевидно, что эта форма определяется не однозначно. Так, используя то, что qÚ`q ≡ 1 и (15), получаем другую конъюнктивную нормальную форму первоначальной формулы: (`pÚq) Ù(`rÚ`q)

Запишем обобщения законов поглощения (7):

рÚ ( р Ù q₁ ) Ú (рÙ q₂ )Ú … Ú (р Ù q_п ) ≡ р (22 1 )

Из них, а также (9), (3), (15)-(18) получаем новые эквивалентности, а значит, правила преобразования, которые позволяют сокращать число переменных, входящих в формулу:

Используя, справа налево дистрибутивный закон (6), получаем два новых соотношения:

(р Ùq ) Ú (р Ùr) ≡ р Ù (q Úr) (27)

(р Úq )Ù (р Úr) ≡ р Ú (q Ùr) (28)

Например, упростить выражение:

(р ÚqÚr) Ù (рÚ qÚ`r ).

Применяя (28), учитывая, что rÙ`r ≡ 0 и (17) получаем:

(р ÚqÚr) Ù (рÚ qÚ`r ) ≡ (р Úq) Ú (rÙ`r ) ≡ р Úq.

Иногда оказывается полезным для упрощения формулы повторить в ней какие-то выражения, используя, справа налево законы поглощения (21)-(22).

Например, упростить выражение

(р Úq )Ù (`рÚq) Ù (`рÚ`q).

Повторим `рÚq и, используя (6), (2), (17), (4) получаем:

(р Úq )Ù (`рÚq) Ù (`рÚq) Ù (`рÚ`q) ≡ (qÚ(рÙ`р)) Ù (`рÚ (qÙ`q)) ≡ (qÚ0) Ù (`рÚ 0) ≡ qÚ`р ≡ `рÚq.

Иногда для каких-то целей необходимо вводить в формулу новые переменные (буквы). Это делается с учетом тождеств (24) и (25) и законов дистрибутивности (6). Так, в выражение р Ú q можно ввести букву r. В самом деле, используя (3), а также (6), получаем:

р Ú q≡(р Úq) Ú (r Ù`r ) ≡ (р ÚqÚr) Ù (рÚ qÚ`r )

4 ДИЗЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА. ПРОБЛЕМА РАЗРЕШИМОСТИ

Для каждой формулы наряду с конъюнктивной нормальной формой существует дизъюнктивная нормальная форма. Она состоит из дизъюнкции конъюнкций, в которой каждый конъюнктивный член является элементарным высказыванием или его отрицанием.

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

Например, привести к дизъюнктивной нормальной форме формулу:

Отрицаем эту формулу и приводим полученное выражение к конъюнктивной нормальной форме:

р Ù (р®q) ≡`рÚ (р ®q) ≡`рÚ (`рÚq) ≡`рÚ (`рÙ`q) ≡(`рÚ`р) Ù(`р Ú`q) ≡ ≡(`рÚр) Ù(`р Ú`q)

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

______________ ____ ______ _ _ _

(`рÚр) Ù(`р Ú`q) ≡(`рÚр) Ú (`р Ú`q) ≡ (`р Ù`р) Ú (`р Ù`q) ≡(р Ù`р) Ú (р Ùq)

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

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

Доказательство получаем из (25)(9 1 ) и (15), а также определения конъюнкции. Так формула (р Ú`рÚ q) Ù( р Ú`qÚ q) тождественно истинна.

Чтобы формула была тождественно ложной необходимо и достаточно, чтобы в ее дизъюнктивной нормальной форме каждый дизъюнктивный член содержал элементарное высказывание вместе со своим отрицанием. Так формула:

(р ÙrÙ`р) Ú ( р Ù r Ù`r ) тождественно ложна.

Доказательство получаем из того, что р Ù`р≡0, (16) и определения дизъюнкции.

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

В самом деле, если это условие для какой-то формулы выполнено, то для этого дизъюнктивного члена существует такой набор значения переменных, для которого он равен 1. Тогда согласно (18) для этого набора значений переменных формула принимает значение, равное1.

Например, докажем, что формула р≡ q выполнима. Приводим эту формулу к дизъюнктивной нормальной форме:

(р≡ q ) ≡(р® q) Ù(q ®р) ≡ (`р Ú q) Ù(`q Úр) ≡((`р Ú q) Ù`q) Ú((`р Ú q) Ùр) ≡ ≡ (`р Ù`q) Ú (q Ù`q) Ú (`р Ù р) Ú (q Ùр) ≡ (`р Ù`q) Ú (q Ùр) ≡ (q Ùр) Ú(`р Ù`q).

Каждый дизъюнктивный член не содержит элементарное высказывание вместе со своим отрицанием. А значит формула р≡ q выполнима.

5 СОВЕРШЕННАЯ ДИЗЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА. СОВЕРШЕННАЯ КОНЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА

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

a) в ней нет двух одинаковых дизъюнкций;

b) ни одна дизъюнкция не содержит двух одинаковых конъюнкций;

c) ни одна дизъюнкция не содержит переменного высказывания вместе со своим отрицанием;

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

Имеется два метода приведения формулы к дизъюнктивной нормальной форме.

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

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

Например, чтобы привести формулу (р®q)Úq®rÚq к дизъюнктивной нормальной форме, составляем таблицу истинности этой формулы. Она имеет вид:

р	q	r	р®q	(р®q)Úq	rÙ q	(р®q)Úq®rÚq
0	0	0	1	1	0	0
0	0	1	1	1	0	0
0	1	0	1	1	0	0
0	1	1	1	1	1	1
1	0	0	0	0	0	1
1	0	1	0	0	0	1
1	1	0	1	1	0	0
1	1	1	1	1	1	1

По сформулированному алгоритму получаем:

(р®q)Úq®rÚq º (`рÙ qÙ r) Ú( р Ù`qÙ`r ) Ú ( р Ù`qÙr)Ú ( р ÙqÙr).

Другой метод приведения формулы к совершенной дизъюнктивной нормальной форме заключается в следующем: приводим формулу к дизъюнктивной нормальной форме, а затем приписываем в каждом дизъюнктивном члене недостающие переменные согласно правилу (24).

Так , для формулы (р®q)Úq®rÚq имеем следующую цепочку преобразований _____________ _____ ____

(р®q)Úq®rÚq º(`рÚ qÚ q) Ú (rÙ q) º`р Úq Ù r Ù q º (`рÚ q)Ù(`qÚ`r ).

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

______________ _ _ _

(`р Ú q)Ù(`qÙ`r ) º(`рÙ`q) Ú (`qÙ`r ) º( р Ù`q) Ú (qÙr).

Затем, пользуясь (24), имеем:

( ( р Ù`q) Ù (r Ú`r)) Ú (( рÚ` р) Ù( qÙr)) º ( р Ù`q Ù r) Ú ( р Ù`q Ù`r) Ú (`рÙ qÙ r) Ú( рÚ q Úr ) º(`рÙ qÙ r) Ú ( р Ù`qÙ`r) Ú( р Ù`qÙr) Ú ( р ÙqÙr).

Аналогичным образом определяется совершенная конъюнктивная нормальная форма какой-то формулы. Она удовлетворяет условиям:

a) в ней нет двух одинаковых конъюнкций;

b) ни одна конъюнкция не содержит двух одинаковых дизъюнкций;

c) ни одна конъюнкция не содержит переменного высказывания вместе со свои отрицанием;

d) в каждой конъюнкции содержится в качестве дизъюнктивных членов все переменные входящие в формулу.

Правила приведения произвольной формулы к совершенной конъюнктивной нормальной форме аналогичны тем, которые были описаны для нахождения совершенной дизъюнктивной нормальной форме и выражаются в двойственных терминах. Так, для формулы (р®q)Úq®rÙq пользуясь ее таблицей истинности и правилом двойственности сразу можно записать совершенную конъюнктивную нормальную форму. Для этого выписываем дизъюнкции переменных, при которых формула истинна, затем расставляем знаки отрицания, чтобы при этих значениях выписанные дизъюнкции обращались в ложь. И наконец соединяем все дизъюнкции знаком конъюнкции. Для предыдущей формулы получаем:

(р®q)Úq®rÙqº( р Ú`qÚ` r) Ù(` р Úq Ú r ) Ù (`рÚqÚ`r) Ù (`рÙ`qÙ`r)

Чтобы привести формулу к совершенной конъюнктивной нормальной форме по другому методу, надо привести ее к конъюнктивной нормальной форме, а затем восстановить в каждом конъюнктивном члене недостающие переменные, пользуясь правилом (23). Так для формулы (р®q)Úq®rÙq имеем следующую цепочку преобразований:

(р®q)Úq® (rÙq) º( `р ÚqÚq) Ú (rÙq) º (`рÙ`q) Ú(rÙq) º (рÙ`q) Ú(rÙq).

По закону двойственности имеем:

(рÙ`q) Ú(rÙq) º (`рÚ`q) Ù (`r Ú`q) º (`рÚq) Ù (`r Ú`q).

В полученной конъюнктивной нормальной форме восстанавливаем недостающие переменные, пользуясь (23).

(`рÚq) Ù (`r Ú`q) º((` р Úq) Ú (rÙ`r)) Ù (( рÚ` р) Ú (`r Ú`q)) º (`рÚ qÚ r) Ù (` рÚ q Ú`r) Ù( рÚ`qÚ`r ) Ù (`рÙ`q Ù` r ).

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

Определение формулы исчисления высказываний, алгебра высказываний. Равносильность формул исчисления высказываний. Совершенная конъюнктивная нормальная форма. Совершенная дизъюнктивная нормальная форма. Проблема решимости, систематические упрощения.

ЛОГИКА ВЫСКАЗЫВАНИЙ

1 ОПРЕДЕЛЕНИЕ ФОРМУЛЫ ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ

2 АЛГЕБРА ВЫСКАЗЫВАНИЙ

3 РАВНОСИЛЬНОСТЬ ФОРМУЛ ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ. КОНЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА

4 ДИЗЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА. ПРОБЛЕМА РАЗРЕШИМОСТИ

5 СОВЕРШЕННАЯ ДИЗЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА. СОВЕРШЕННАЯ КОНЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА

1 ОПРЕДЕЛЕНИЕ ФОРМУЛЫ ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ

Пропозициональная переменная есть формула

Всякая формула есть либо пропозициональная переменная или образуется из пропозициональных переменных последовательным применением правила 2).

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

Опускаются скобки, объемлющие отдельные переменные.

2 АЛГЕБРА ВЫСКАЗЫВАНИЙ

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

Читайте также: