Сделай Сам Свою Работу на 5

Тождества логики высказываний





Отрицание

Символически отрицание записывается как ùА, где А - сложное или простое высказывание, а символ ù означает опе­рацию отрицания. Читается: «Неверно, что A». Если отрицается сложное высказывание, то знак ù ставится перед всем сложным высказыванием, которое заключается в скобку. Например: ù(AÚB).

Дадим определение операции отрицание.

Отрицание - логическая операция, превращающая истин­ное высказывание в ложное, а ложное высказывание в истинное.

Пример: Волга впадает в Балтийское море. Высказывание ложное, поэтому его отрицание дает истинное высказывание: Неверно, что Волга впадает в Балтийское море.

Другое высказывание: 2 меньше 5. Высказывание истинное. По­этому его отрицание порождает ложное высказывание: Неверно, что 2 меньше 5.

Операцию отрицания можно определить через так называемую таблицу истинности. Введем два дополнительных символа. Истинность высказывания будем обозначать еди­ницей – 1, ложность высказывания будем обозначать нулем – 0.

  Таблица истинности для отрицания    
A   ùA   ù ùA

 



Первая строчка таблицы показывает, что если исходное выска­зывание A истинно, то его отрицание ùА ложно. Вторая строчка пока­зы­вает, если исходное высказы­вание является ложным, то его отрицание будет истинным высказыванием. На основании данной таблицы можно также вывести логическое тождество или равенство высказывания А и его двойного отрицания ù ùА (не­верно, что неверно, что А). Это тождество можно записать так:ù ùА º А. Здесь символ º означает логическое тождество, или равенство. Можно сформулировать правило двойного отрицания:

Двойное отрицание высказывания тождественно исходному высказыванию.

Примеры:

1. Молекула озона состоит из 3-х атомов кислорода.

Высказывание истинно, поэтому его отрицание дает ложное высказывание: Неверно, что молекула озона состоит из 3-х атомов кис­лорода. Но двойное отрицание исходного высказывания дает снова истинное высказывание: Неверно, что неверно, что молекула озона состоит из3-хатомов кислорода.

2. Полуостров Таймыр – родина апельсинов.



Высказывание ложно, его отрицание дает истинное высказы­вание: Неверно, что полуостров Таймыр – родина апельсинов. Двойное отрицание исходного высказывания порождает снова ложное высказывание: Неверно, что неверно, что полуостров Таймыр – родина апельсинов.

Задание 1. Проведите отрицание и двойное отрицание нижеследующих вы­сказываний и определите истинностное значение полученных вы­сказываний на основании истинностных значений исходных вы­сказываний.

Марс является планетой Солнечной системы.

По понедельникам на Гавайских островах выпадает снег.

Неверно, что Марс является планетой Солнечной сис­темы.

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

Конъюнкция

Сложное высказывание, образованное при помощи конъюнкции, называ­ется конъюнктивным, или соединительным, высказыванием.

Символическая запись такого высказывания: А·В·С·..., где А, В, С – сложные или простые высказывания, точка · означает операцию конъюнкции. Могут использоваться также символы Ç, Ù, & или символ вообще может отсутствовать. При­меры записи: AÇBÇC, или АÙВÙС, или А&В&С, или АВС. Читается: А конъюнкция В конъюнкция С.

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

В русском языке операции конъюнкции соответствуют союзы “и”, “а”, “но”, “да”, “однако”, “зато”, “хотя”, “не смотря на”, “не только..., но и...”, просто запятая, точка с запятой. Конъ­юнктивным высказыванием может быть совокупность предложе­ний, разделенных точками. Примеры:



Корень учения горек, зато плоды его сладки. (Посл.)

Мал золотник, да дорог. (Посл.)

Встает заря во мгле холодной;

На ниве шум работ умолк. (Пушкин)

Стада шумят, и соловей

Уж пел в безмолвии ночей. (Пушкин)

Был вечер. Небо меркло. Воды

Струились тихо. Жук жужжал.

Уж расходились хороводы. (Пушкин)

    Таблица истинности для конъюнкции      
A B A·B B·A

 

Таблица показывает, что высказывание А·В является истин­ным лишь в том случае, когда истинно высказывание А и истинно высказывание В. Во всех ос­тальных случаях высказывание А·В является ложным. Дадим определение операции конъюнкции.

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

Рассмотрим примеры конъюнкций независимых по смыслу высказываний.

Сумма углов треугольника равна 180°, и Волга впадает в Балтийское море.

Сумма углов треугольника равна 180°, и Волга впадает в Каспийское море.

Сумма углов треугольника равна 90°, и Волга впадает в Каспийское море.

Сумма углов треугольника равна 90°, и Волга впадает в Балтийское море.

Согласно определению конъюнкции лишь второе конъюнктивное высказывание является истинным, остальные три - ложные.

При помощи таблицы истинности можно вывести правило ком­мутативности конъюнкции: при перестановке членов конъюн­ктивного высказывания его истинностное значение не меняется.

Правило коммутативности позволяет отличать предложения, которые тоже могут быть соединены союзом “и”, запятой и т.д., но не образуют конъюнктивного высказывания. Рассмотрим пример:

Анисья тотчас к ней явилась.

И дверь пред ними отворилась.

И Таня входит в дом пустой. (Пушкин)

Здесь мы не можем переставлять местами отдельные предложения, так как налицо последовательность во времени. Следовательно, это не конъюнктивное высказывание.

Задание 4. Определите, какие фрагменты из “Евгения Онегина” Пуш­кина можно охарактеризовать как конъюнктив­ные высказывания.

Нигде, ни в чем ей нет отрад...

И облегченья не находит

Она подавленным слезам,

И сердце рвется пополам.

И входит на пустынный двор.

К ней, лая, кинулись собаки.

На крик испуганный ея

Ребят дворовая семья

Сбежалась шумно.

И в одиночестве жестоком

Сильнее страсть ее горит,

И об Онегине далеком

Ей сердце громче говорит.

Татьяна в лес; медведь за нею;

Снег рыхлый по колено ей.

Упала в снег; медведь проворно

Ее хватает и несет;

Она бесчувственно-покорна,

Не шевельнется, не дохнет.

Задание 5. Определите истинностные значения конъюнктивных выска­зываний.

7 является четным числом, и Волга впадает в Балтийское море, однако, произведение чисел 8 и 5 равно 70.

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

Дизъюнкция

В логике высказываний различают два вида дизъюнкции: сла­бую (нестрогую) дизъюнкцию, которую часто называют просто дизъюнкцией, и мы ее также будем называть; и сильную (строгую) дизъюнкцию. Рассмот­рим сначала один вид, затем другой.

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

Символическая запись дизъюнктивного высказывания AÚВÚСÚ..., где А, В, С – сложные или простые высказывания, символ Ú означает операцию дизъюнкции. Может также использо­ваться символ È. Например, АÈВÈС. Читается: А дизъюнкция B дизъюнкция С. В простейшем случае могут объ­единяться два высказывания: АÚВ. Члены дизъюнктивного высказывания называются альтернативами.

В русском языке слабой дизъюнкции соответствуют союзы “или”, “либо”. Пример дизъюн­ктивного высказывания:

В отпуск я уеду на море или проведу какое-то время на даче.

    Таблица истинности для слабой дизъюнкции  
A B AÚB BÚA

 

Таблица показывает, что высказывание AÚB является ложным, лишь когда ложны обе альтернативы A и B – четвертая строка. Во всех остальных случаях дизъюнктивное высказывание AÚB является истинным. Из таблицы видно, что дизъюнктивное высказывание коммутативно.

Определение слабой дизъюнкции.

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

Вернемся к дизъюнктивному высказыванию «В отпуск я уеду на море или проведу какое-то время на даче». Это высказывание окажется ложным, если не состоятся ни поездка на море, ни отдых на даче. Но высказывание будет истинным, если будет осуществлено что-то одно либо и то, и другое.

Этот треугольник либо равносторонний, либо равнобед­ренный.

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

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

Символическая запись сильной дизъюнкции: AÑBÑCÑ …, где А, В, С – сложные или простые высказывания, сим­вол Ñ означает операцию строгой дизъюнкции.

В русском языке строгой дизъюнкции соответствуют те же со­юзы, что и слабой дизъюнкции, т.е. “или“, “либо”. Используются так­же удвоенные союзы “или..., или”, “либо..., либо”. Пример исключающе-разделительного высказывания:

Это натуральное число является четным либо является нечетным.

Чтобы определить вид дизъюнкции, можно поставить перед всем высказыванием выражение «Одно из двух (трех, четырех…). Если высказывание сохранит смысл, значит, имеем дело с сильной дизъюнкцией.

Так, вполне можно сказать: «Одно из двух: это натуральное число является четным либо является нечетным». Но получится бессмыслица, если мы скажем «Одно из двух, это натуральное число четное, либо делится на 3 без остатка», потому что вполне возможно, что данное число, обладает как тем, так и другим свойством; таково, например, число 6.

    Таблица истинности для сильной дизъюнкции  
A B AÑB BÑA

 

Таблица показывает, что высказывание AÑB является истинным, когда одна, и лишь одна, из альтернатив является истинной - строчки 2, 3. Во всех остальных случаях высказывание AÑB является ложным. Сильная дизъюнкция коммутативна.

Определение сильной дизъюнкции.

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

Рассмотрим примеры:

Треугольник АВС является либо прямоугольным, либо он является ту­поугольным, либо является остроугольным.

Слоны обитают либо на Аляске, либо обитают в Австралии.

Слоны обитают либо в Австралии, либо обитают в Африке, либо обитают в Азии.

Из этих высказываний первое является истинным, так как объединяются сильной дизъюнкцией такие вы­сказывания, из которых одно обязательно является истинным. Второе высказывание ложно, т.к. сильной дизъюнкцией объ­единяются два ложных простых высказывания. В самом деле, бессмысленно утверждать, что одно из двух: либо слоны обитают на Аляске либо в Австралии, так как слоны обитают совсем в других местах. Третье выска­зывание тоже ложно, т.к. сильной дизъюнкцией объединя­ются три простых высказывания, из которых два - второе и третье - являются истинными, поэтому нельзя использовать выражение «одно из трех…». Но это же высказывание о слонах будет истинным, если мы истолкуем союзы «либо..., либо...» как слабую дизъюнкцию, так как при слабой дизъюнкции могут быть истинными больше, чем одна альтернатива. В таком случае изменится формула высказывания: не AÑBÑC, но AÚBÚC.

Рассмотрим с логической точки зрения фрагменты из «Евгения Онегина» Пушкина.

Я жду тебя: единым взором

Надежды сердца оживи

Иль сон тяжелый перерви

Увы, заслуженным укором!

Быть может, он для блага мира

Иль хоть для славы был рожден.

В первом случае союз “иль” означает сильную дизъюнкцию, т.к. не может быть и то, и другое, лишь что-то одно. Во втором случае союз “иль” означает слабую дизъюнкцию, так как возможно одновременно как то, так и другое.

Задание 6. Определите вид дизъюнкции:

Не дай мне Бог сойтись на бале

Иль при разъезде, на крыльце

С семинаристом в желтой шали

Иль с академиком в чепце!

Паду ли я, стрелой пронзенный,

Иль мимо пролетит она.

Все благо: бдения и сна

Приходит час определенный.

Импликация

Сложное высказывание, полученное при помощи импликации, называ­ется импликативным, или условным, высказыванием. Первый член в таком сложном высказывании называется основанием, или антецедентом, второй – следствием, или консеквентом.

Символическая запись импликативного высказывания: А®В, где A и B – сложные или простые высказывания, символ ® означает операцию импликации. Может использоваться символ É, например, АÉВ. Читается: А имплицирует В.

В русском языке операции импликации соответствуют союз «если A, то B», а также выражения: «коль скоро A, то B»; «кто A, тот B», «для A необходимо B»,«А, только если B», «поскольку A, пос­тольку B», «В,если A», «там B, где A»; «тогда B, когда A», «А доста­точно для B» и т.п. Могут использоваться тире и запятая. Примеры им­пли­ка­тив­ных высказываний:

Если вода нагревается, то она испаряется.

Тише едешь – дальше будешь.

Подальше положишь – поближе возьмешь.

Кто беден, тот тебе не пара. (Грибоедов)

Подписано, так с плеч долой. (Грибоедов)

Он знак подаст – и все хохочут.

Он пьет – все пьют и все кричат. (Пушкин).

Мы видим, что грамматические союзы могут быть самые раз­личные или вообще отсутствовать. Здесь нет какого-то четкого единого правила, кроме одного: выражение, соответствующее импликативному высказыванию, всегда можно преобразовать без утери исходного смысла в предложение с союзом «если..., то...». Например:

Если беден, то тебе не пара.

Если подписано, то с плеч долой.

Если он знак подаст, то все хохочут.

    Таблица истинности для импликации    
A B A®B B®A

 

Таблица истинности показывает, что высказывание A®B яв­ляется истинным во всех случаях, кроме случая, когда основание ис­тинно, а следствие ложно. Импликация, в отличие от предыдущих операций, некоммутативна: от перестановки членов значение импликативного вы­сказывания может изменяться. Так, ложности выражения B®A соответ­ствует уже не вторая строчка, но третья.

Определение операции импликации:

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

Обычно возникает вопрос, почему импликативное высказывание A®B является истинным, когда основание A ложно, а следствие B истинно, или: как можно содержательно понять истинность высказывания типа «если ложь, то истина» (третья строчка таблицы)?

Рассмотрим высказывание «Если прошел дождь, то асфальт мокрый», т.е. А®В. Допустим, что А ложно, т.е. на самом деле дождя не было. Может ли, тем не менее, асфальт оказаться мокрым? И здесь мы должны согласиться с тем, что это вполне возможно. Асфальт может оказаться мокрым по другим причинам: прошла поливальная машина, дворник полил асфальт и т.п. Но асфальт может оказаться и сухим, а не мокрым. Этим двум случаям как раз и соответствуют 3-я и 4-я строчки таблицы: 0®1 и 0®0. Сделаем несколько неожиданный, но с логической точки зрения вполне правомерный вывод: если основание ложно, то следствие может быть как истинным, так и ложным.

Единственная ситуация, которая невозможна, следующая: дождь про­шел, а асфальт остался сухим, т.е. не мокрым. Этой ситуации как раз и соответствует 2-я строчка: 1®0.

Иногда операцию импликации отождествляют с причинной связью, т.е. A®B понимают так, что A порождает B. На самом деле импликация может выражать не только причинные, но и самые разнообразные связи: например, последовательность во времени: «Прошла зима, настало лето», или свойства чисел: «Если число четное, то оно оканчивается на четное число», также другие связи. Важно одно, что импликативное высказывание является ложным, если первый член истинен, а второй ложен, в остальных случаях высказывание истинно. Импликация может связывать высказывания совершенно независимые по смыслу. Рассмотрим такие случаи:

Если сумма углов треугольника равна 180°, то Волга впа­дает в Балтийское море.

Если сумма углов треугольника равна 180°, то Волга впа­дает в Каспийское море.

Если сумма углов треугольника равна 90°, то Волга впа­дает в Балтийское море.

Если сумма углов треугольника равна 90°, то Волга впа­дает в Каспийское море.

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

Задание 7. Определите истинност­ное значение следующих импликативных высказываний.

Если 7 – четное число, то истиной является все что угодно.

Если 7 – нечетное число, то истиной является не все что угодно.

Если истиной является все что угодно, то 7 – четное число.

Если истиной не является все что угодно, то и 7 не есть четное число.

Если истиной не является все что угодно, то 7 – четное число.

Если истиной является все что угодно, то 7 – нечетное число.

Если 7 – четное число, то истиной не является все что угодно.

Если 7 нечетное число, то истиной является все что угод­но.

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

и тождественные преобразования

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

Однако высказывания, вообще говоря, могут включать несколь­ко операций, причем различного вида. Рассмотрим следующие примеры:

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

Скоро мы поедем в Москву и, если у нас будет достаточно времени, то погуляем по Красной площади.

Формула первого высказывания: a·ùb®(cÚd), в ней 4 перемен­ных: а, в, с, d и 4 операции: конъюнкция, отрицание, импликация, слабая дизъюнкция.

Формула второго высказывания: а·(b®с), в ней 3 переменных и 2 операции: конъюнкция и импликация.

Как определять истинностные значения сложных высказываний, ко­торые строятся на нескольких операциях? Или по-другому – при каких значениях переменных a, b, с... высказывание будет истинным, а при каких – ложным?

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

Сначала дадим правила построения таких таблиц.

Правило 1. Число строчек таблицы истинности равно 2n, где п – число переменных в формуле.

Допустим, что переменных в формуле всего 2, т.е. а и b. Поэтому строчек в таблице будет 22 = 4.

Но допустим, что число переменных равно 3 – а, b, с. Тогда строчек будет 23 = 8. При 4-х переменных строчек будет 16 и т.д.

Правило 2. Распределение истинностных значений переменных в столбцах должно обеспечивать перебор всех комбинаций значений «истина» и «ложь» данного числа пе­ременных.

Для этого в столбце первой переменной 1, т.е. «истина», проставля­ется в первой половине строчек 0, т.е. «ложь», проставляется во второй половине строчек.

В столбце второй переменной 1 проставляется уже в первой четверти общего числа строчек, 0 – во второй четверти общего числа строчек, далее 1 проставляется в третьей четверти числа строчек, 0 – в оставшейся четверти строчек.

В столбце третьей переменной 1 проставляется в первой восьмой части всего числа строчек, 0 – в сле­дующей восьмой части общего числа строчек, далее 1 проставляется в третьей восьмой части, 0 в четвер­той восьмой части общего числа строчек. Снова 1 про­ставляется в следующей восьмой части строчек и т.д.

Словесное описание этого принципа выглядит громоздким, но его легко по­нять на конкретных примерах построения таблиц.

Таблица с 1-й переменной  
а

 

Таблица с 2-мя переменными  
а b

 

 

Таблица с 3-мя переменными
а B с

 

 

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

Смысл правила состоит в том, чтобы не делать лишних ско­бок. Поясним на примерах. Имеем формулу a·ùb®(cÚd). Сначала вы­полняем отрицание ùb, затем конъюнкцию a·ùb, затем операцию в скобках, т.е. дизъюнкцию cÚd, и заключительной операцией бу­дет импликация a·ùb®(cÚd). Пронумеруем операции на самой фор­муле:

a·2ùb1®4(cÚ3d).

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

a·2ùb1®3cÚ4d.

Другой пример. Формула а·(b®с). Сначала выполняем опера­цию в скобках, т. е. импликацию, затем конъюнкцию. Пронумеру­ем операции:

а·2(b®1с).

Еще примеры: а·3b1®2с); (a®1b) ·3ùb2®5ùa4.

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

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

Формула этого высказывания: а·(ùb®с). Переменных в высказы­вании 3, следовательно, в таблице, согласно Правилу 1, будет 8 строчек (23). Строим таблицу. В этой таблице мы проставили ис­тинностные значения переменных а, b, c согласно Правилу 2. Со­гласно Правилу 3 выполнили сначала операцию ùb и проставили соответствующие значения в столбце под выражением ùb в формуле.  
a b c а·(ùb®с)
10 1
10 1
11 1
01 0
00 1
00 1
01 1
01 0

 

Затем выполнили операцию ùb®с, проставив соответствующие ис­тинностные значения под импликацией.

Наконец, выполнили конъ­юнкцию, проставив под ней окончательные значения всего высказы­вания в целом. Эти значения выделили жирным шрифтом.

Что можно теперь сказать о данном высказывании в целом? Мы обна­руживаем, что это высказывание истинно лишь в трех случаях.

Первый – когда истинны одновременно высказывания a, b и с, т.е. когда Петров дей­ствительно в отпуск поехал на юг и даже в шторм каждый день купался в море.

Второй – когда истинны высказывания a и b, а высказывание с ложно, т.е. в отпуск Петров поехал на юг, но в шторм не купался.

Третий – когда истинны высказывания а и с, а высказывание b ложно, т.е. в отпуск Петров поехал, и купался в море, когда оно не штормило.

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

Рассмотрим другой пример.

Скоро мы поедем в Москву, и, если у нас будет достаточно времени, то погуляем по Красной площади.

Формула высказывания а·(b®с). Строим таблицу истинности.

Согласно таблице высказывание истинно лишь в трех случаях. Первый – мы поехали в Москву, времени было достаточно, и мы погуляли по Красной площади. Второй – мы поехали в Москву, и, несмотря на нехватку времени, мы все-таки погуляли по Красной площади. Третий – мы поехали в Москву, и из-за нехватки времени по Красной площади не погуляли.
a b c а·(b®с)
1 1
0 0
1 1
1 1
0 1
0 0
0 1
0 1

 

В остальных случаях высказывание ложно. Например, в слу­чае, когда мы поехали в Москву, и времени там у нас было доста­точно, но по Красной площади мы не погуляли – 2-я строчка.

Задание 8. Сформулируйте, опираясь на таб­лицу, остальные случаи ложного высказывания о поездке в Москву.

Задание 9. В качестве упражнения постройте таблицу истинности сложного высказывания «Дитя не плачет, мать не разумеет». Определите, в каких случаях это высказывание будет истинным, а в каких – ложным.

Тавтологии.Построим общую таблицу истинности для ниже следующих формул. В этой таблице используются прописные латинские буквы, означающие как простые, так и сложные высказывания. Так, например, в формуле A®B вместо A и B могут быть подставлены простые высказывания или высказывания, имеющие слож­ную структуру.

A B A®A AÚùA   ù(A·ùA) A®(B®A)   (A®BA®B
1 0 1 0 0 1 1 1 1 1
1 0 1 0 0 1 1 0 0 1
1 1 1 0 1 1 0 1 0 1
1 1 1 0 1 1 1 1 0 1

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

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

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

если светит солнце, то светит солнце, a®a;

солнце светит или неверно, что солнце светит, aÚùa;

неверно, что солнце светит и в то же время не светит,ù(a·ùa);

если светит солнце, то, если идет дождь, то светит солнце, a®(b®а);

если идет дождь, то асфальт мокрый, дождь идет, - значит, асфальт мокрый,(a®ba ® b.

Тавтологии лежат в основе логических зако­нов и умозаключений в логике высказываний, которые мы будем рассматривать в соответствующих разделах.

Логические тождества. Построим общую таблицу истинности для других формул и тоже присмотримся к ней внимательно.

A B A®B ùAÚB ù(A·ùB) ù(AÚB) ùA·ùB ùAÚùB ù(A·B)
0 1 10 0 0 1 0 0 0 0 0 0 0 1
0 0 01 1 0 1 0 0 1 0 1 1 1 0
1 1 10 0 0 1 1 0 0 1 1 0 1 0
1 1 10 1 1 0 1 1 1 1 1 1 1 0

Можно заметить, что пары формул 1 и 2, 1 и 3, 4 и 5, 6 и 7 имеют одинаковое распределение истинностных значений. Это означает, что они логически тождественны. Запи­шем это их свойство в виде тождеств.

A®B º ùAÚB;

A®B ºù(A·ùB);

ù(AÚB)ºùA·ùB;

ùAÚùB º ù(A·B);

Итак, мы имеем логические тождества. Дадим их определение.

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

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

Тождества логики высказываний

  1. A®B º ùAÚB 2. A®B º ù(A·ùB)   правила устранения импликации
  3. A®B º ùB®ùA   правило контрапозиции
  4. ù(AÚB) º ùB·ùA 5. ù(A·B) º ùAÚùB   правила де Моргана
6. A·B º B·A 7. AÚB º BÚA   правила коммутативности
8. AÚA·B º A 9. A·(AÚB) º A   правила поглощения
10. A·(BÚC) º (A·B)Ú(A·C) 11. AÚB·C º (AÚB)·(AÚC)   правила дистрибутивности
12. (AÚB)·(CÚD) º A·C Ú A·D Ú B·C Ú B·D правило раскрытия скобок
  13. ù ùA º A правило двойного отрицания
14. AÚA º A 15. A·A º A   правила равносильности (идемпотентности)
16. AÚ(BÚC) º (AÚBC 17. A·(B·C) º (A·BC   правила ассоциативности
  18. AÚùA º 1  
  19. A·ùA º 0  
20. AÚ1 º 1  
21. AÚ0 º A  
22. A·1 º A  
23. A·0 º 0  
  24. A·ùA·B º 0  
  25. AÚùAÚB º 1  
  26. A·ùAÚB º B  
  27. (AÚùAB º B  
  28. AÑB º A·ùBÚB·ùA правило удаления сильной дизъюнкции

Разъясним смысл некоторых тождеств. Правила де Моргана[2] выражают взаимосвязь дизъюнкции и конъюнкции, которая состоит в следующем:

− отрицание дизъюнкции высказываний тождественно конъюнкции отрицаний этих высказываний;

− отрицание конъюнкции высказываний тождественно дизъюнкции отрицаний этих высказываний.

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

Правила равносильности, или идемпотентности, означают, что дизъюнкция или конъюнкция одинаковых высказываний равны этим высказываниям. Например, сложное высказывание «Идет дождь, и идет дождь» тождественно простому высказыванию «Идет дождь».

Тождества 18 и 19 означают, что дизъюнкция высказывания и его отрицания всегда будет истинной, а их конъюнкция - всегда ложной. Например, истинным будет высказывание «Идет дождь или не идет дождь», и ложным высказывание «Идет дождь, и не идет дождь».

Смысл остальных тождеств попробуйте уяснить сами.

Задание 10. Докажите при помощи таблицы истинности правила поглощения, а также тождества 20, 21, 22, 23.

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

Докажем тождество 24, т.е. A·ùA·B º 0.

1. A·ùA·B º0·В – заменили формулу A·ùA на 0 в соответствии с тождеством 19.

2. 0·B º B·0 см. тождество 6.

3. В·0 º 0 - см. тождество 23.

Итак, доказано, что A·ùA·B º 0.

Перепишем доказательство в виде цепочки, указывая при знаке º но­мер используемого тождества: A·ùA·B º19В º6 В·0 º23 0.

Доказательство тождества 25: AÚùAÚB º18B º7 BÚ1 º20 1. Таким образом: AÚùAÚB º 1.

Доказательство тождества 12: (AÚB)·(CÚ

 








Не нашли, что искали? Воспользуйтесь поиском по сайту:



©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.