Site Loader

Содержание

ЛОГИЧЕСКИЕ ОПЕРАЦИИ (КОНЪЮНКЦИЯ, ДИЗЪЮНКЦИЯ, ИНВЕРСИЯ, ИМПЛИКАЦИЯ, ЭКВИВАЛЕНТНОСТЬ)

Занятие № 23,24

дата

группа

__.__.____

 

Тема: Логические операции (конъюнкция, дизъюнкция, инверсия, импликация, эквивалентность)

 

Цель: Познакомить с основными логическими операциями:

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

Задачи:

1.                       Сформировать у учащихся понятие “логическая операция»;

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

Ожидаемые результаты:

Учащиеся должны знать:

·              логические операции: инверсия, конъюнкция, дизъюнкция, импликация, эквивалентность

;

·              таблицы истинности логических операций;

·              обозначение логических операций;

·              приоритет логических операций.

Учащиеся должны уметь:

·              определить порядок действий при вычислении значения логического выражения;

·              конструировать простые и сложные высказывания.

 

Ход урока

I. Организационный момент.

II. Проверка домашнего задания.

III. Изложение нового материала.

     Основным понятием математической логики является понятие «простого высказывания». Под высказыванием обычно понимают всякое повествовательное предложение, утверждающее что-либо о чем-либо, и при этом мы можем сказать, истинно оно или ложно в данных условиях места и времени. Логическими значениями высказываний являются «истина» и «ложь».

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

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

Отрицание (инверсия)
Отрицанием высказывания х называется новое высказывание    , которое является истинным, если высказывание х ложно, и ложным, если высказывание х истинно. 
Отрицание высказывания х обозначается       и читается «не х» или «неверно, что х». 
Логические значения высказывания        можно описать с помощью таблицы. 
Таблицы такого вида принято называть таблицами истинности. 

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

Дизъюнкция
Дизъюнкцией (логическим сложением) двух высказываний х и у называется новое высказывание, которое считается истинным, если хотя бы одно из высказываний х, у истинно, и ложным, если они оба ложны.
Дизъюнкция высказываний х, у обозначается символом «x V у» , читается «х или у» . Высказывания х, у называются членами дизъюнкции. 
Логические значения дизъюнкции описываются следующей таблицей истинности: 

 

Импликация.
Импликацией двух высказываний х и у называется новое высказывание, которое считается ложным, если х истинно, а у — ложно, и истинным во всех остальных случаях.
Импликация высказываний х, у обозначается символом        , читается«если х, то у» или «из х следует у». 
Логические значения операции импликации описываются следующей таблицей истинности: 

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

Упражнение 1. Даны два простых высказывания:

А= “Аист – птица”;

В=“Щука — речная рыба”.

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

 

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

1.                       инверсия

2.                       конъюнкция

3.                       дизъюнкция

4.                       импликация и эквивалентность

Операции одного приоритета выполняются слева направо. Для изменения порядка действий используются скобки.

Например: дана формула .

Порядок вычисления:

 — инверсия

 — конъюнкция

— дизъюнкция

 — импликация

 — эквивалентность.

IV. Закрепление изученного материала.

1. Какие из предложений являются высказываниями? Определите их истинность.

1. Какой длины эта лента?

2. Прослушайте сообщение.

3.Делайте утреннюю зарядку!

4. Назовите устройство ввода информации.

5. Кто отсутствует?

6. Париж — столица Англии. (ЛОЖЬ)

7. Число 11 является простым. (ИСТИНА)

8. 4 + 5=10. (ЛОЖЬ)

9. Без труда не вытащишь и рыбку из пруда.

10. Сложите числа 2 и 5.

11. Некоторые медведи живут на севере.(ИСТИНА)

12. Все медведи — бурые. (ЛОЖЬ)

13.Чему равно расстояние от Москвы до Ленинграда.

 

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

1.                       Число 456 трехзначное и четное.

2.                       Неверно, что Солнце движется вокруг Земли.

3.                       Число делится на 9 тогда и только тогда, когда сумма его цифр делится на 9.

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

5.                       Чтобы погода была солнечной, достаточно, чтобы не было ни ветра, ни дождя.

6.                       Если человек с детства и юности своей не давал нервам властвовать над собой, то они не привыкнут раздражаться, и будут ему послушны.

 

3. Постройте отрицания следующих высказываний.

1.                       На улице сухо.

2.                       Сегодня выходной день.

3.                       Ваня не был готов сегодня к урокам.

4.                       Неверно, что число 3 не является делителем числа 198.

5.                       Неверно, что число 17 — простое.

 

4. Запишите следующие высказывания в виде логических выражений.

1.Число 17 нечетное и двузначное.

2. Неверно, что корова — хищное животное.

4. Если число делится на 2, то оно — четное. Переходи улицу только на зеленый свет.

6. На уроке информатики необходимо соблюдать особые правила поведения.

8. Если Маша — сестра Саши, то Саша — брат Маши.

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

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

5. По данным формам сложных высказываний запишите высказывания на русском языке.

1.                      

2.                        

3.                      

 

6. Найдите значения логических выражений:

1.                      

2.                      

3.                      

4.                      

5.                      

6.                      

7.                      

 

7. Даны простые высказывания: А= {15>13}, В={4=5}, C= {7<4}. Определите истинность составных высказываний:


 

8. Какие из высказываний А, В должны быть истинны и какие ложны, чтобы было ложное высказывание ?

V. Итог урока.

Обобщить пройденный материал, оценить работу активных учеников.

VI. Домашнее задание.

1. Выучить определения, знать обозначения.

2. Даны высказывания:

А = {На улице светит солнце},

В = {На улице дождь},

С = {На улице пасмурная погода},

D = {На улице идет снег}.

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

Задача 1

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

1.Андрей старше Светы. Наташа старше Светы.

2.Один десятый класс идет на экскурсию в музей. Второй десятый класс идет в театр.

3.На полке стоят учебники. На полке стоят справочники.

4.   Часть детей — девочки. Остальные — мальчики.

Задача 2

Для логических выражений сформулируйте составные высказывания на обычном языке:

1) (Y>1 и Y<3) или (Y<8n Y>4)

2) (Х=Y)и (X=Z)

3) Не (Х<0) и Х<10 или (Y>0)

4) (0<Х) и (Х<5) и (не(Y<10))

 


 

10 2 4 основные логические операции (инверсия дизъюнкция конъюнкция)

10.24. Основные логические операции (инверсия, дизъюнкция, конъюнкция).

Понятие логической операции Инверсия Дизъюнкция Конъюнкция Свойства логических операций

1. Понятие логической операции.

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

Под высказыванием понимают повествовательное предложение, относительно которого имеет смысл говорить, однозначно истинно оно или ложно. Высказывания принято обозначать большими буквами латинского алфавита: А, В, С… и т.д. Если высказывание С истинно, то пишут С = 1, а если оно ложно, то С = О.

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

2. Инверсия.

Логическим отрицанием или инверсией называется присоединение частицы «не» к данному высказыванию. Это логическая операция обозначается ‘А и читается «не А» . Если высказывание А истинно, то ‘А ложно, и наоборот. Таблица истинности в этом случае имеет вид (слева).

3. Дизъюнкция. Логическим сложением или дизъюнкцией называется объединение двух или нескольких высказываний с помощью союза «или».

На формальном языке алгебры логики операция логического сложения записывается следующим образом: Z = X + Y или Z = X v Y. Аргументами здесь являются логические переменные X и Y, которые могут принимать значения истина (1) к ложь (0).

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

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

Для функции логического сложения (дизъюнкции) таблица истинности будет выглядеть следующим образом:

X

Y

Z = XvY

0

0

0

0

1

1

1

0

1

1

1

1

Примером высказывания на естественном языке, содержащего дизъюнкцию, может служить следующее высказывание: «Капусту можно употреблять в пищу в свежем, тушеном или соленом виде».Y

0

0

0

0

1

0

1

0

0

1

1

1

В естественном языке конъюнкция выражается с помощью союзов «и», «а», «но», «как Х, так и Y», «не только X, но и Y», «Y, несмотря на X», «X вместе с Y», «X в то время как Y» и т. (Y v Z)

3.4. Основные логические операции над высказываниями. Логика и аргументация: Учебн. пособие для вузов.

3.4. Основные логические операции над высказываниями

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

1. Любое высказывание в классической логике имеет одно и только одно из двух значений истинности — «истину» или «ложь». С этой точки зрения истинностное значение будущих событий остается неопределенным.

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

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

Определение логических операций

Простейшей из логических операций является отрицание, с помощью которого из данного высказывания образуется противоречащее ему высказывание. В обычном языке операция выражается словами «неверно, что» или просто «не», в символическом — знаком отрицания, поставленным перед высказыванием. Если дано высказывание х, то его отрицание будет -x. В обычной речи отрицание чаще всего стоит перед глаголом и именной частью сказуемого. Например, отрицанием высказывания «2 есть четное число» будет высказывание «Неверно, что 2 есть четное число», которое ложно. Отрицая его, получим высказывание «Неверно, что 2 не есть четное число», которое равнозначно высказыванию «2 есть четное число». Это означает, что двойное отрицание приводит к первоначальному высказыванию. Обратите внимание, что высказывание, полученное путем отрицания первоначального, является противоречащим ему, т.е. оно отрицает нечто, но не утверждает что-то. Так, когда мы говорим, что «этот лист бумаги не белый», то не утверждаем, что он зеленый, синий или фиолетовый.

Для определения отрицания используется матрица (таблица) истинности, в которой в левой колонке даются два значения истинности («истина» и «ложь») первоначального высказывания, а в правой колонке — его отрицания (табл.1). Истинность высказывания будет обозначаться буквой «и» или числом 1, ложь — буквой «л» и числом 0.

Если высказывание истинно, то противоречащее ему высказывание будет ложно, и, наоборот, если высказывание ложно, то противоречащее высказывание будет истинно.

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

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

Дизъюнкция (логическая сумма) двух или нескольких простых высказываний образуется путем объединения их логической связкой «или». Союз «или» в языке чаще всего употребляется в исключающем смысле, когда происходит выбор между двумя альтернативами: либо одно, либо другое. Реже используется этот союз в неисключающем смысле, т.е. выражается словом «а также». В логике и математике связка «или» употребляется преимущественно в неисключающем смысле. Так, например, дизъюнкция «2 меньше 3 или 3 меньше 5» понимается в неисключающем смысле, так как не только 2, но и 3 меньше 5.

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

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

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

Условное высказывание состоит из двух простых высказываний. То из них, которое вводится словом «если», называется антецедентом (предыдущим высказыванием), а также основанием, а начинающееся словом «то» — консеквентом (последующим высказыванием) или следствием условного высказывания.

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

В обычной речи часто не проводят различия между основанием и следствием, как логическим отношением, и причиной и следствием, как отношением реального мира. Убедиться в наличии причинной связи можно лишь путем конкретного исследования явлений окружающего нас мира. Если одно явление вызывает или порождает другое явление, то первое из них мы называем причиной, а второе — следствием. Так, нагревание стержня — причина — вызывает его удлинение — следствие. Эту зависимость мы устанавливаем эмпирически — путем наблюдения и измерения. Логическое отношение между основанием и следствием не нуждается в эмпирическом исследовании, так как устанавливается с помощью чисто логических рассуждений. В нашем примере равенство углов равностороннего треугольника выводится как геометрическая теорема.

Условные высказывания употребляются для выражения самых разнообразных отношений между высказываниями, но не во всех случаях при этом учитывается их содержание и смысл. В современной логике обращается внимание исключительно на связь между высказываниями по значению их истинности, потому что задача логики состоит в том, чтобы гарантировать истинность заключения из истинных посылок, а для этого необходимо перенести истинность с посылок на заключение. В связи с этим в логической импликации абстрагируются (отвлекаются) от содержания и смысла и обращают внимание только на связь высказываний по значению их истинности. В результате можно рассматривать импликации, которые выглядят бессмысленными и парадоксальными с точки зрения обычного, здравого смысла. Например, «Если 2 х 2 = 5, то Москва — большой город» считается не только допустимой, но и истинной импликацией.

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

Например, импликация «Если 2 х 2 = 4, то Москва — небольшой город» является ложной, так как ее антецедент — истинное высказывание, а консеквент — ложное.

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

Распределение значений истинности высказываний для импликации представлено табл.4, где стрелка обозначает импликацию.

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

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

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

Кроме табличного определения логические операции (за исключением отрицания) можно определить через другие, с обязательным использованием отрицания. Действительно, применив табличный метод (табл. 6), можно убедиться, что выражения (х ? у) и (¬у ?¬x) будут эквивалентными, т.е. (х?у) ? (¬у?¬х).

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

С помощью таблиц истинности можно проверить, что и остальные логические операции можно определить через Другие две, причем второй операцией всегда будет отрицание. Например, дизъюнкцию можно выразить через конъюнкцию: (х ? у) ? (¬x ? ¬у).

Способ установления истинности сложных высказываний, образованных из простых с помощью таблицы, был предложен американским логиком Ч.С. Пирсом и оказался весьма удобным. Как мы видели, этот способ основывается на комбинации значений истинности простых высказываний и последующего определения истинности сложных высказываний, образованных с помощью операций отрицания, конъюнкции, дизъюнкции и импликации. Например, когда имеется два высказывания, то число различных комбинаций из их значений истинности будет равно 4, при трех — 8, при четырех — 16, а следовательно, при заданном числе п оно равно 2n. Отсюда нетрудно заметить, что определение истинности сложного высказывания сводится в сущности к вычислению ее на основе значений истинности простых высказываний. Это впечатление усилится, если мы обозначим истину как 1, а ложь как 0 и будем их комбинировать, чтобы образовать отрицание, конъюнкцию, дизъюнкцию и т.д. В качестве иллюстрации вычислим значение истинности следующего выражения: (х ? у) ? (х ? z).

При некотором навыке процесс вычисления можно ускорить, обратив главное внимание на основную операцию, которая связывает две части формулы. В приведенном примере (табл. 7) достаточно заметить, что ложная импликация возникает при истинном антецеденте и ложном консеквенте. Отсюда легко определить возможные значения х и у в дизъюнкции (х ? у), а также значения х и z в конъюнкции (х ? z). Такой сокращенный способ вычисления истинности сложного высказывания основывается на установлении главной логической операции в рассматриваемой формуле.

Законы логики высказываний

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

Закон тождества: если х, то х, т.е. х ? х.

Закон упрощения: если х и у, то х, т.е. х?у?х. То же самое относится к другому конъюнктивному члену: х?у? у

Закон эквивалентности: если из х следует у, а из у следует х, тогда высказывания эквивалентны, т. е. x ? у.

Закон гипотетического силлогизма: если из х следует у, а из у следует z, то из х следует z, т.е.

((x ? y) ? (y ? z)) ? (x ? z)

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

¬ (¬x) ? x

Законы О. де Моргана дают возможность переходить от конъюнкции к дизъюнкции и, наоборот, от дизъюнкции к конъюнкции. Они служат удобным средством для преобразования высказываний:

а) отрицание конъюнкции высказываний эквивалентно дизъюнкции из отрицаний конъюнктивных членов:

¬ (x ? y) ? (¬x ? ¬y)

б) отрицание дизъюнкции эквивалентно конъюнкции отрицаемых членов дизъюнкции:

¬ (x ? y) ? (¬x ? ¬y)

Закон «поглощения»: конъюнкция или дизъюнкция одинаковых высказываний эквивалентна самому высказыванию, т.е. повторяющийся член «поглощается»:

(x ?x) ? x и (x ? x) ? x.

Коммутативные законы для конъюнкции и дизъюнкции разрешают перестановку их членов:

(x ? y) ? (x ? y) и (x ? y) ? (y ? x).

Ассоциативные законы для конъюнкции и дизъюнкции позволяют по-разному сочетать члены, т.е. по-иному расставлять скобки:

x ? (y ? z) ( ? x ? y) ? z или x ? (y ? z) ( ? x ? y) ? z.

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

(x ? y) (¬ ? y ? ¬x)

Закон противоречия: два противоречащих друг другу высказывания, т.е. высказывание х и его отрицание не-х, не могут быть вместе истинными:

(x ? ¬x)

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

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

x ? ¬x

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

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

Все законы исчисления высказываний, как в этом можно убедиться с помощью таблиц истинности, являются тождественно истинными (общезначимыми формулами). Какие бы истинностные значения не придавались входящим в них высказываниям, в конечном счете формула оказывается всегда истинной. Вот почему эти законы явно или неявно применяются в любом рассуждении, ибо именно с их помощью становится возможным преобразовать и упрощать имеющуюся информацию и приходить к определенным заключениям. Поясним это на примере закона контрапозиции. Если нам известно, что «треугольник х равнобедренный», то отсюда следует высказывание у, утверждающее, что «углы при его основании равны». Но если эти углы не равны, то по закону контрапозиции можно заключить, что «треугольник не является равнобедренным», т.е. (х ? у) ? (¬y ? ¬x). Таким образом, этот вывод мы получаем чисто логически, не прибегая, например, к доказательству методом от противного.

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

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

Логические математические соединители: соединения и дизъюнкции — видео и расшифровка урока

Connectors

Если у вас есть два оператора и вы хотите их объединить, вы можете добавить либо «и», либо «или» между двумя операторами. Каждый имеет разное значение. Давайте посмотрим, что они из себя представляют. Мы также увидим, как эти соединители влияют на комбинированное составное утверждение с точки зрения его маркировки как истинного или ложного.

Союзы

Когда два утверждения связаны союзом «и», получается союз .Для союзов только тогда, когда оба утверждения верны, комбинированное составное утверждение является истинным.

Например, если бы у нас были два утверждения «квадраты — это прямоугольники» и «круги — это овалы», и мы объединили их с «и», чтобы получить составное утверждение «квадраты — это прямоугольники, а круги — это овалы», это новое составное утверждение утверждение истинно только тогда, когда истинны два утверждения, с которых мы начали. Если только одно истинно, а другое ложно, составное утверждение также ложно.

То же самое было бы верно, если бы нашими двумя утверждениями были «Джон любит шоколадное мороженое» и «Сью любит клубничное мороженое».Если мы объединим их с «и», чтобы получить «Джон любит шоколадное мороженое, а Сью любит клубничное мороженое», то два утверждения должны быть истинными, чтобы составное утверждение было истинным.

Дизъюнкция

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

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

Аналогично для составного утверждения «Джон любит шоколадное мороженое или Сью любит клубничное мороженое». Если утверждение «Джон любит шоколадное мороженое» верно, а утверждение «Сью любит клубничное мороженое» ложно, то составное утверждение остается верным из-за соединителя «или».

Итоги урока

Давайте подытожим то, что мы узнали. Утверждения — это любые фразы, которые можно пометить как истинные или ложные.Чтобы объединить два утверждения, мы можем добавить либо «и», либо «или» между двумя утверждениями, чтобы сформировать новое составное утверждение.

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

Результаты обучения

После изучения этого урока вы сможете сделать следующее:

  • Распознать высказывание
  • Определите союз, используемый для объединения операторов
  • Подчеркните важность разъемов
  • Укажите признаки дизъюнкции

Союзы и дизъюнкции в математике (видео, определение и примеры)

Содержание

В математической логике слова имеют точное значение.Логика пытается показать правдивые выводы, вытекающие из правдивых предпосылок, или надежно выявляет ложь. Математические и логические операторы соединяются соединителями; конъюнкции и дизъюнкции — это два типа логических соединителей.

  1. Логические операторы
  2. Логические разъемы
  3. Союзы в математике
  4. Дизъюнкции в математике
  5. Примеры конъюнкции и дизъюнкции

Логические операторы

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

  1. Все числа целые
  2. Некоторые отрицательные числа являются целыми числами
  3. Квадраты являются прямоугольниками
  4. Некоторые четырехугольники являются параллелограммами
  5. Четырехугольники имеют 11 сторон
  6. Прямоугольники имеют четыре стороны

Ясно, что некоторые из этих шести утверждений ложны, но дело в том, что их можно проверить.Они не высказывают мнения. Сравните их, скажем, «Мне нравятся чизбургеры», что показывает мнение.

Логические разъемы

Утверждения часто обозначаются буквами p и q. Они связаны вместе с помощью соединителей, поэтому вы можете комбинировать идеи, используя «и» или «или» между утверждениями. Два оператора, соединенные соединителями, создают составной оператор . Соединение логических утверждений — это не то же самое, что связывание идей в обычном английском разговоре.Сравните:

  • Я люблю чизбургеры, а мой друг любит банановые молочные коктейли
  • Все числа целые, а квадраты прямоугольники

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

Два типа соединителей называются союзами («и») и дизъюнкциями («или»). В союзах используется математический символ ∧, а в дизъюнкциях — математический символ ∨.

Союзы в математике

Соединение двух утверждений с помощью «и» представляет собой союз , что означает, что оба утверждения должны быть истинными, чтобы составное утверждение в целом было истинным. Соединения обозначаются символом ∧, поэтому эти два отдельных оператора можно объединить в составной оператор:

.
  • Утверждение p: Квадраты — это прямоугольники
  • Утверждение q: прямоугольники имеют четыре стороны
  • Составное утверждение (на английском языке): Квадраты — это прямоугольники, а прямоугольники имеют четыре стороны.
  • Составной оператор (в математических символах): p∧q

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

Дизъюнкции в математике

Когда связующим звеном между двумя операторами является «или», у вас есть дизъюнкция . В этом случае только одно утверждение в составном утверждении должно быть истинным, чтобы все составное утверждение было истинным.

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

  1. Все числа целые
  2. Некоторые отрицательные числа являются целыми числами
  3. Квадраты являются прямоугольниками
  4. Некоторые четырехугольники являются параллелограммами
  5. Четырехугольники имеют 11 сторон
  6. Прямоугольники имеют четыре стороны

Если мы свяжем одно истинное и одно ложное утверждение в составное утверждение, используя соединитель «или» (обозначается ∨), мы все равно получим истинное составное утверждение:

  • p: Квадраты прямоугольники
  • q: Четырехугольники имеют 11 сторон
  • p∨q: Все квадраты являются прямоугольниками или четырехугольниками с 11 сторонами

Примеры конъюнкции и дизъюнкции

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

  • p: Некоторые отрицательные числа являются целыми числами
  • q: Квадраты являются прямоугольниками
  • Некоторые отрицательные числа являются целыми числами, а квадраты — прямоугольниками.

Вы сказали p∧q и оценили ли вы это как истину? Оба утверждения верны, поэтому составное утверждение, соединенное союзом «и», истинно.

  • p: Некоторые четырехугольники являются параллелограммами
  • q: Четырехугольники имеют 11 сторон
  • Некоторые четырехугольники являются параллелограммами, или четырехугольники имеют 11 сторон.

Вы сказали p∨q и оценили это составное утверждение как истинное? Хотя у четырехугольников нет 11 сторон, союз «или» делает составное утверждение верным, поскольку некоторые четырехугольники являются параллелограммами.

  • p: Четырехугольники имеют 11 сторон
  • q: Прямоугольники имеют четыре стороны
  • Четырехугольники имеют 11 сторон, а прямоугольники имеют четыре стороны.

Вы сказали p∧q? Что еще более важно, вы сказали, что это составное утверждение было ложным? Поскольку у четырехугольников нет 11 сторон, конъюнкция неверна.

  • p: Все числа целые
  • q: Квадраты являются прямоугольниками
  • Все числа являются целыми числами или квадраты являются прямоугольниками.

Вы написали p∨q? Вы сказали, что это ложно, поскольку обе части составного утверждения ложны?

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

Следующий урок:

Обратное, Обратное, Противоположное

Соединители 3B

Соединители 3B

3B Коннекторы

Связка — это слово, используемое для объединения двух утверждений в одно, например и , или , потому что , однако и т. д. или , самые простые связки.Соединение операторов с и называется соединением , а соединение операторов с или называется дизъюнкцией . Логический символ «и» — «Ù», а символ «или» — «Ú». Выражение, образованное путем объединения двух или более выражений с помощью связок, является составным высказыванием .

пример 1

 

 

Обед с Фредом

Пусть p, q, r и s будут утверждениями


р : я ездил в город

r : Я встретил Фреда

q : Я обедал

s: Я купил туфли.

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


p Ù q : Я был в городе и пообедал

q Ù ~r : Я обедал и не встретил Фреда

r Ú q : Я встретил Фреда или пообедал

p Ù r Ù ~s : Я поехал в город, встретил Фреда и не купил обувь

q Ù (r Ú s) : Я пообедал, встретил Фреда или купил обувь

(q Ù r) Ú s: Я пообедал и встретил Фреда, или я купил обувь

~(p Ù r) : Я не поехал в город и не встретился с Фредом

(p Ù s) Ú (r Ù q) : Я пошел в город и купил туфли, или я встретил Фреда и пообедал

~(s Ú ~q) : Я не покупал обувь и не пропускал обед.




Таблица истинности
для соединения

р

q

р Ù кв

Т

Т

Т

Т

Ф

Ф

Ф

Т

Ф

Ф

Ф

Ф

 

Что мы имеем в виду, когда соединяем два утверждения словом «и»? Например, если вы говорите «Я встретил Фреда и пообедал», что вы хотите, чтобы люди поняли из этого составного утверждения? В самом деле, вы хотите, чтобы слушатели приняли за истину утверждение «Я встретил Фреда», а также утверждение «Я обедал»; если какое-либо из этих простых утверждений ложно, то все ваше сложное утверждение ложно.Таким образом, когда вы говорите «p и q», вы говорите правду, если и p истинно, и q истинно, но вы говорите ложно, если либо p ложно, либо q ложно, либо если оба p и q ложны. Мы суммируем эти наблюдения в таблице истинности слева. В первых двух столбцах таблицы перечислены все возможные значения истинности общих утверждений p и q, а в третьем столбце приведены соответствующие значения истинности в каждом случае для союза p Ù q.

 

Анализ связки «или» несколько сложнее, потому что в разных обстоятельствах мы можем интерпретировать эту связку по-разному.В повседневном использовании есть два вида «или» — исключающее или и включительно или . Предположим, например, что вы завтракаете в ресторане Zippys, и официантка объявляет, что «вы можете съесть рис или оладьи с яйцами». Она, вероятно, имеет в виду, что без дополнительной оплаты вы можете есть рис с яйцами или оладьи с яйцами, в зависимости от ваших предпочтений, но , а не , что у вас может быть и рис, и оладьи.В этом случае она использует исключение или , потому что тот или иной вариант должен быть исключен. Теперь предположим, что официантка спрашивает: «Вы хотите посолить или поперчить яйца?» Теперь она, вероятно, имеет в виду, что у вас может быть соль на яйцах, у вас может быть перец на яйцах или даже соль и перец на яйцах. Здесь она использует включительно или , что означает, что не обязательно исключать один из вариантов.

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

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

р

q

р У к

Т

Т

Т

Т

Ф

Т

Ф

Т

Т

Ф

Ф

Ф

 

Какой же тогда будет наша таблица истинности для «или»? Предположим, вы пришли на свадебный прием, и швейцар спрашивает, были ли вы приглашены женихом или невестой (очевидно, используя «включающее или» в этой ситуации).Если вы ответите: «Да, меня пригласила невеста или меня пригласил жених», при каких обстоятельствах вы говорите правду? Если любое из утверждений

р : Меня пригласила невеста

q : Меня пригласил жених

истинно, или даже если оба p и q истинны, то ваше составное утверждение p Ú q истинно. Вы лжете швейцару, только если оба p и q ложны. Таким образом, дизъюнкция p Ú q ложна только тогда, когда и p, и q ложны, и истинна во всех остальных ситуациях.Прилагаемая таблица истинности для дизъюнкции суммирует эти наблюдения.

Наши таблицы истинности для отрицания, конъюнкции и дизъюнкции можно обобщить следующим списком «логических уравнений»:

 

Т Ù Т = Т

 

Т У Т = Т

~F = T

T Ù F = F

Т Ú F = Т

F Ù T = F

F Ú T = T

Ф Ù Ф = Ф

F Ú F = F .

Эти формулы имеют очевидные интерпретации. Например, ~T = F указывает, что отрицание истинного утверждения является ложным утверждением, тогда как T Ù F = F утверждает, что соединение истинного утверждения и ложного утверждения является ложным утверждением.

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

пример 2

Предположим, что утверждение p истинно, утверждение q ложно, а утверждение r истинно.Определяем истинность составных утверждений

а. (~p Ú q) Ù r

 

б. (p Ù ~r) Ú (q Ú r)

 

г. ~(q Ú r) Ù (~p Ú q) .

В каждом из этих выражений мы подставляем T вместо p и r и подставляем F вместо q; тогда упрощаем:

а.

(~T Ú F) Ù T

 

б.

(T Ù ~T) Ú (F Ú T)

 

г.

~(F Ú T) Ù (~T Ú F)

(F Ú F) Ù T

(Т Ù Ж) Ú Т

~T Ù (F Ú F)

Ф Ù Т

ФУТ

Г Ù Г

Ф

Т

Ф

Мы заключаем, что утверждения частей a и c ложны, тогда как утверждения части b верны.



пример 3

 

Вернувшись поздно домой, г-н Ким сделал жене следующее заявление:

«Я не успел на автобус, или я работал допоздна и не успел на автобус».

Мы воспользуемся таблицей истинности, чтобы определить, при каких обстоятельствах г-н Ким говорит правду. Путем определения простых операторов

р : Я сел на автобус

 

q : Я работал допоздна ,

можно написать Mr.Составное утверждение Кима как

~p Ú (q Ù p) .

 

р

q

~

q Ù p

~p Ú (q Ù p)

Т

Т

Ф

Т

Т

Т

Ф

Ф

Ф

Ф

Ф

Т

Т

Ф

Т

Ф

Ф

Т

Ф

Т

Мы строим таблицу истинности для этого утверждения, начиная со столбцов для p и q слева и добавляя столбцы до тех пор, пока не построим Mr.Заявление Кима в последней колонке. Первые два столбца не требуют никакой работы — они просто перечисляют все возможные значения истинности p и q — но оставшиеся столбцы мы заполняем, используя предыдущие столбцы и наши логические уравнения для отрицания, конъюнкции и дизъюнкции. Обратите внимание, что третий столбец отрицает первый столбец, четвертый столбец представляет собой соединение первых двух столбцов, а последний столбец представляет собой дизъюнкт третьего и четвертого столбцов. Таблица истинности показывает, что утверждение мистера Кима ложно только тогда, когда p истинно, а q ложно; при всех других условиях он говорит правду.Следовательно, г-жа Ким может сделать вывод, что либо г-н Ким говорит правду, либо он лжет, сел на автобус и не опоздал на работу.



Далее мы обдумываем, как отрицать конъюнкцию. Это поможет посмотреть на конкретном примере. Пусть p и q будут утверждениями

р : собака коричневая

 

q: собака ленивая,

и рассмотрим соединение этих утверждений,

pÙq: собака коричневая и ленивая.

 

Отрицанием p Ù q является утверждение, истинностное значение которого должно быть противоположно истинностному значению p Ù q, независимо от обстоятельств. Итак, предположим, что p Ù q ложно, то есть предположим, что ложно то, что собака коричневая и ленивая. Тогда какое утверждение должно быть верным? Собака должна быть либо «не коричневой», либо «не ленивой», то есть утверждение ~p Ú ~q должно быть истинным. С другой стороны, предположим, что p Ù q истинно, так что собака коричневая и ленивая; тогда ложно, что собака не коричневая и не ленивая, поэтому утверждение ~p Ú ~q ложно.Следовательно, поскольку p Ù q и ~p Ú ~q обязательно противоположны по истинностному значению, отрицание p Ù q равно

.

~p Ú ~q: собака не коричневая и не ленивая.

Этот пример иллюстрирует так называемый закон де Моргана для отрицания конъюнкции ,


~(p Ù q) ≡ ~p Ú ~q .

Опять же, символ «≡» указывает на то, что два утверждения эквивалентны. Мы строго проверяем эту формулу с помощью приведенной ниже таблицы истинности. В таблице мы включили столбцы для каждого из утверждений ~(p Ù q) и ~p Ú ~q.Поскольку последовательность Т и F одинакова в этих двух столбцах, утверждения всегда имеют одно и то же истинностное значение и, таким образом, логически эквивалентны.


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

р

q

~

~q

р Ù кв

~(p Ù q)

~p Ú ~q

Т

Т

Ф

Ф

Т

Ф

Ф

Т

Ф

Ф

Т

Ф

Т

Т

Ф

Т

Т

Ф

Ф

Т

Т

Ф

Ф

Т

Т

Ф

Т

Т

пример 4

Слева появляются некоторые союзы, а справа их отрицания:


СОЕДИНЕНИЕ

ОТРИЦАНИЕ

Лэнс высокий и красивый.

 

Лэнс не высокий и не красивый.

Мэри и Бет здесь.

Мэри или Бет здесь нет.

Я устал и потерял бдительность.

Я не устал и не в сознании.

Конгрессмен не демократ и либерал.

Конгрессмен является демократом или не либералом.



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

.

p : в мопеде нет бензина

 

q: мопед сломан,

а также их разъединение,

p Ú q: в мопеде нет бензина или он сломан.

 

Если p Ú q ложно, то мопед не кончился и не сломался, поэтому и ~p, и ~q истинны, т. е. истинна конъюнкция ~p Ù ~q.С другой стороны, если p Ú q верно, то либо в мопеде нет бензина, либо он сломан, либо, возможно, и то, и другое, поэтому ложно, что мопед не кончился и не сломан, то есть ~p Ù ~q ложно. Следовательно, поскольку p Ú q и ~p Ù ~q всегда противоположны по истинностному значению, отрицание p Ú q равно

.

~p Ù ~q: мопед исправен и не сломан.

Этот пример демонстрирует закон де Моргана для отрицания дизъюнкции ,


~(p Ú q) ≡ ~p Ù ~q .

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

пример 5

Слева появляются некоторые дизъюнкции, а справа их отрицания:


РАЗЪЕДИНЕНИЕ

ОТРИЦАНИЕ

Эдит дома или болеет.

 

Эдит нет дома и она не больна.

Его брат богат или знаменит.

Его брат не богат и не знаменит.

Яйцо протухло или несвежее.

Яйцо не тухлое и свежее.

Пришло время ловить рыбу или нарезать наживку.

Не время ловить рыбу и не время резать наживку.



Можно, конечно, связать сразу несколько утверждений словом «и», а также словом «или». Два таких примера

1)  Эйб Линкольн был хузером, железнодорожником и юристом.

2)  Эйб Линкольн был хузером, или железнодорожником, или юристом.

 

Предположение в первом утверждении состоит в том, что все три утверждения верны, а не только одно или два из них. Составное утверждение вида p Ù q Ù r истинно, когда истинны все три утверждения p, q и r, и ложно при всех остальных условиях. Напротив, второе утверждение утверждает только то, что по крайней мере одно из трех утверждений истинно — не обязательно, что два или три из них истинны.Составное утверждение p Ú q Ú r ложно, если все три утверждения p, q и r ложны, и истинно при всех остальных условиях.

Мы суммируем эти размышления в следующей таблице истинности для трех утверждений p, q и r. В трех левых столбцах таблицы перечислены все возможные комбинации значений истинности p, q и r; их восемь, в результате получается таблица из восьми строк. (По соглашению первые три столбца в таблице истинности для трех утверждений всегда заполняются именно таким образом.) В последних двух столбцах перечислены соответствующие значения истинности для конъюнкции p Ù q Ù r и дизъюнкции p Ú q Ú r. Справа от таблицы находятся соответствующие логические уравнения, утвержденные таблицей.


р

q

р

п Ù кв Ù г

p q Ú r

Т

Т

Т

Т

Т

Т

Т

Ф

Ф

Т

Т

Ф

Т

Ф

Т

Т

Ф

Ф

Ф

Т

Ф

Т

Т

Ф

Т

Ф

Т

Ф

Ф

Т

Ф

Ф

Т

Ф

Т

Ф

Ф

Ф

Ф

Ф

 

Т х Т х Т = Т

 

Т У Т У Т = Т

Т Ù Т Ù F = F

 

Т У Т У Ф = Т

T Ù F Ù T = F

 

T Ú F Ú T = T

T Ù F Ù F = F

 

T Ú F Ú F = T

F Ù T Ù T = F

 

F Ú T Ú T = T

F Ù T Ù F = F

 

F Ú T Ú F = T

F Ù F Ù T = F

 

F Ú F Ú T = T

F Ù F Ù F = F

 

F Ú F Ú F = F

Формулы для отрицания конъюнкций и дизъюнкций трех утверждений:

~(p Ù q Ù r) ≡ ~p Ú ~q Ú ~r

,

~(p Ú q Ú r) ≡ ~p Ù ~q Ù ~r .

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


1)   

Я закажу спагетти, салат и чай.

Я не буду заказывать ни спагетти, ни салат, ни чай.

2)   

Я приду в понедельник, вторник или среду.

Я не приду ни в понедельник, ни во вторник, ни в среду.


 

Благодаря богатству нашего языка в повседневной беседе мы можем говорить одно и то же по-разному. Союз «и», например, может стоять в нескольких формах. Пусть p и q будут утверждениями

p : Джек пошел в гору

,

q : Джилл осталась лежать .

Вот различные способы, которыми мы можем сделать логическое утверждение p Ù q :

1)

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

2)

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

3)

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

4)

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

5)

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

6)

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

7)

Джек пошел в гору; более того, Джилл осталась лежать.

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

УПРАЖНЕНИЯ 3B


  1. Пусть p, q, r и s будут утверждениями

    p : лошадь ушла

    ,

    q : ворота закрыты

    ,

    r : корова мычит

    ,

    с: наступают сумерки.

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

     

    а.

    р Ù р

     

    б.

    ~p Ù q

     

    г.

    р Ус

     

    д.

    р Ù ~q Ù с

    эл.

    r Ú (p Ù s)

    ф.

    (r Ú p) Ù s

    г.

    ~(p Ù ~q)

    час.

    (s Ù p) Ú ~q

    я.

    (~r Ú p) Ù ~s

    л.

    (p Ù s) Ú (q Ù ~r)

    к.

    ~q Ú ~p Ú r

    л.

    кв Ù ~(р Ù с)


  2. Пусть p, q, r и s будут утверждениями

    p : детский плач

    ,

    q : детский смех

    ,

    r : ребенок голоден

    ,

    s: ребенок устал.

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

    а.

    Ребенок плачет и голоден.

    б.

    Ребенок плачет, голоден или устал.

    в.

    Малыш не голоден, но смеется.

    д.

    Ребенок плачет, устал и голоден.

    эл.

    Ребенок устал или голоден и не смеется.

    ф.

    Ребенок плачет, голоден или устал.

    г.

    Малыш смеется и не устает или голоден и плачет.

    з.

    Дело не в том, что Малыш устал и голоден.

    и.

    Ребенок голоден или устал, плачет и не смеется.

    л.

    Малыш смеется, или Малыш не голоден, устал и плачет.


  3. Определите, является ли «или» в предложении включающим или исключающим:

     

    а.

    Лист клена или вяза.

    б.

    Я надеюсь получить пятерку или четверку в этом классе.

    в.

    Завтра будет облачно или дождливо.

    д.

    На обед я всегда ем фрукты или овощи.

    эл.

    Джим любит эскапистские или смешные фильмы.

    ф.

    Дай мне свободу или дай мне смерть.


  4. Предположим, утверждения p и q верны, а r и s ложны. Определите истинность каждого из следующих составных утверждений:

    а.

    р Ù р

     

    б.

    q Ú s

     

    г.

    (~p Ù с) Ú q

    д.

    (q Ú r) Ù ~s

    эл.

    (q Ú ~s) Ù (r Ú ~p)

    ф.

    ~s Ù (p Ú ~q)

    г.

    (s Ù p) Ú ~(r Ù q)

    час.

    (~p Ù s) Ú (p Ù q Ù r)

    я.

    ~(~q Ú r) Ù (s Ú p Ú ~r)


  5. Постройте таблицу истинности для каждого утверждения:

    а.

    р Ú ~q

     

    б.

    ~p Ù q

     

    г.

    р Ù (q Ú ~р)


  6. Политик пообещал: «Я буду голосовать за снижение налогов или за фискальную реформу и не буду голосовать за фискальную реформу». Что должен сделать политик, чтобы сдержать свое слово? Обоснуйте свой ответ таблицей истинности.
  7. Используйте таблицу истинности, чтобы проверить закон де Моргана для отрицания дизъюнкции.
  8. Дайте отрицание каждого утверждения:

       

    1. Я буду усердно учиться и сдам экзамен на пятерку.
    2. Мальчик старше 16 лет или в сопровождении родителей.
    3. Арахисовое масло липкое и прилипает к нёбу.
    4. Я понимаю вашу позицию и не сержусь.
    5. Дженни не поедет ни в Париж, ни в Рим.
    6. Земля не плоская и не лежит на спине черепахи.
    7. Жителя квартиры нет дома или он спит.
    8. Мэри выиграет гонку или умрет, пытаясь.

  9. Проверьте каждую формулу отрицания с помощью таблицы истинности:

    а.

    ~(p Ù q Ù r) ≡ ~p Ú ~q Ú ~r

     

    б.

    ~(p Ú q Ú r) ≡ ~p Ù ~q Ù ~r


 
  1. Дайте отрицание каждого утверждения:
    1. Баскетбольная команда UH обыграет Райс, Фресно и Талсу.
    2. UH проиграет Неваде, СМУ или Бойсе.
    3. Команда будет усердно тренироваться, играть умно и не терять надежду.
    4. Мы выиграем игру — или по крайней мере постараемся — или тренер не быть довольным.
    5. Энди, или Бен, или Карл, или Дэн составят команду конференции.
    6. Я буду наслаждаться игрой, есть попкорн, кричать с чирлидершами, и послушайте группу.

  1.  

    Пусть p и q будут утверждениями

    p : Боб принесет еду

    ,

    q : Бев принесет напитки .

    Запишите составные утверждения символически:
    1. Боб принесет еду, а Бев принесет напитки.
    2. Боб принесет еду, а Бев не принесет напитки.
    3. Боб принесет еду, а Бев принесет напитки.
    4. Боб не принесет еды; Бев не принесет напитки.
    5. Бев принесет напитки; кроме того, Боб принесет еду.
    6. Хотя Бев принесет напитки, Боб не принесет еды.
    7. Несмотря на то, что Боб не принесет еды, тем не менее Бев принесет напитки.
    8. Бев принесет напитки; в качестве альтернативы Боб принесет еду.

Логика и доказательство

Логика и доказательство

Введение

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

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

целей для этого Глава:

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

Введение

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

Логическое следствие

Первое из двух понятий — это ЛОГИЧЕСКОЕ ПОСЛЕДСТВИЕ , что в значительной степени именно то, на что это похоже — понятие что одно логически следует из другого.Если слово следствие напоминает вам о следствие условного, то вы получаете право идея. Вот формальное определение:

Определение:

Q — это ЛОГИЧЕСКОЕ ПОСЛЕДСТВИЕ из П тогда и только тогда, когда P → Q — тавтология.

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

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

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

Итак, если мы хотим определить логическое следствие с точки зрения истинностных назначений, то мы бы сказали, что Q является логическим следствием P тогда и только тогда, когда каждое присваивание истинностного значения, которое делает P true также делает К правда. Это в точности эквивалентно нашему определению с точки зрения условного, что приводит нас ко второму двух наших понятий, ЛОГИЧЕСКАЯ ЭКВИВАЛЕНТНОСТЬ .

Логическая эквивалентность

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

С точки зрения истинностных назначений, понятие логической эквивалентности можно определить следующим образом: два формулы логически эквивалентны тогда и только тогда, когда они присваивается одно и то же значение истинности для каждого присвоения значения истинности. Как насчет определения в терминах связки? Так так необходимо ввести новую связку, чтобы отразить понятие эквивалентность в том смысле, что условное выражение отражает понятие логического следствия.Мы назовем эту новую связку ДВУХКОНДИЦИОНАЛЬНЫЙ , и использовать символ ↔ для этого. Теперь мы можем дать наше определение логической эквивалентности:

Определение:

P логически эквивалентен Q тогда и только тогда, когда П ↔ Q является тавтологией.

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

Итак, как нам заполнить это таблица истинности? Ну, мы знаем из нашей первой характеристики логическая эквивалентность, которая Р и Q логически эквивалентны тогда и только тогда, когда они приписаны одно и то же истинностное значение для каждого присваивания истинностного значения.Мы знаем по нашему формальному определению в терминах бикондиционала, что они логически эквивалентны на всякий случай P ↔ Q — тавтология. Соединив эти два вместе, мы знаем это Р и Q будет присвоено одно и то же значение истинности для каждого значения истинности. задание на всякий случай P ↔ Q является тавтологией, т. е. истинной для любого значения истинности. назначение. Ах ха! Это означает, что P ↔ Q верно на всякий случай Р и Q имеют одинаковое истинностное значение для данного задания, и ложно, если они этого не делают.Вот наша заполненная таблица истинности для биусловный:

п Вопрос П ↔ Q
Т Т Т
Т Ж Ж
Ж Т Ж
Ф Ф Т

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

Введение

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

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

  1. Каждое предложение письмо P — правильно построенная формула сентенциальной логики.
  2. Если P — правильно построенная формула сентенциальной логики, тогда так ¬П.
  3. Если Р и Q — правильно построенные формулы сентенциальной логики, то же самое относится и к каждому из следующих:

    • ( П и В )
    • ( П против Q )
    • ( П → Q )
    • ( Р ↔ Q )
  4. Ничто не является хорошо сформированной формулой сентенциальной логики, если только ее существование таковым не следует из (одного или более) первые три правила.

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

  1. Сначала вставьте скобки вокруг каждого появление & и это два конъюнкта, начиная с крайнего правого & .
  2. Затем вставьте скобки в том же мода на в .
  3. Теперь вставьте скобки для →.
  4. Наконец, вставьте скобки для ↔.
  5. Правые скобки никогда не должны быть вставлены внутри другого набора скобок, т. е. не разбивать до существующей пары.

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

Правила исключения и введения

а. П ↔ Q    
б. п    
..    
д. Вопрос     ↔EL: а, б
а. П ↔ Q    
б. Вопрос    
..    
д. п     ↔ER: а, б
а. | п Предположение
.. |    
в. | Вопрос    
.. |    
эл. | Вопрос Предположение
.. |    
г. | п    
ч. П ↔ Q     ↔I: а, а

Эквиваленты для поездок на работу

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

а. П ↔ Q    
..    
в. Q ↔ П     CommBiCond: и

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

Замена эквивалентов

Наше следующее правило для бикондиционала вполне немного отличается от других правил, которые мы видели до сих пор. Этот один позволяет ЗАМЕНА подформулы на строке в выводе — замена другой формулой, который, как известно, эквивалентен первому.Вот само правило:

а. П ↔ Q    
б. п    
..    
д. Вопрос     RE: а, а

Строки b и c могут выглядеть немного странно. Вот как «прочитать» это правило: если у вас есть бикондиционал на одна строка вывода и формула с участием первого эквивалентов этого бикондиционала на другом (строка б), вы можете вывести из них формулу, которая получается замена первого эквивалента вторым равномерно по всей формуле в строке b.

Вот простой пример:

ПРИМЕР:
Вывод: Q → (P v R)
1. Q → Т Прем
2. T ↔ (P v R) Прем
3. Q → (P v R)     RE: 2, 1

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

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

Введение

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

Бикондиционал

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

п Вопрос П ↔ Q ( П → Q ) & ( Q → П)
Т Т Т Т Т Т
Т Ж Ж Ж Ж Т
Ж Т Ж Т Ж Ж
Ж Ж Т Т Т Т

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

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

Конъюнкция, дизъюнкция, и законы ДеМоргана

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

Итак, как именно мы можем определить, скажем, соединение P & Q, используя законы ДеМоргана, видя поскольку в нем нет отрицаний П и В? С небольшой помощью двойного отрицания, конечно. Если мы дважды отрицаем P&Q мы получаем ¬¬(P & Q), что по ДеМоргану эквивалентно ¬(¬P v ¬Q).Аналогично, дизъюнкция P v Q эквивалентно ¬(¬P и ¬Q).

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

Введение

Так что же ИСТИННО-ФУНКЦИОНАЛЬНАЯ ПОЛНОТА , и какое это имеет отношение к определению связок? Заметим, прежде всего, что любая формула п языка сентенциальной логики можно рассматривать семантически как функция истинности: для любого значения истинности она имеет уникальное истинностное значение! Если п содержит, n букв предложения, пусть !П обозначают n-местную функцию истинности, выраженную как П.Ну, истинно-функциональная полнота языка «а» для сентенциальная логика (например, определенный набор логических связок) является это свойство: для любой возможной функции истинности существует формула языка, который ее выражает. Говоря в терминах определения связок, функционал истинности полнота может быть описана как свойство быть в состоянии определить все возможные связки.

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

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

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

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

п Вопрос в &
Т Т Т Т Т Т Т Т Т Т F F F F F F Ф Ф
Т Р Т Т Т Т F F F F Т Т Т Т F F Ф Ф
F Т Т Т F F Т Т F F Т Т F F Т Т Ф Ф
F F Т Р Т Р Т Р Т Р Т Р Т Р Т F Т Ж

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

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

На самом деле, прежде чем мы перейдем к испытательной части, мы должны полностью прояснить, что именно мы будем доказывать.Вот он:

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

Мы разобьем это на пару более простых задач, одну из которых мы уже выполнили.Первой задачей будет доказать, что каждая возможная функция истинности может быть выражена формулой в ДИЗЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА — особый тип формулы, включающей только отрицание, дизъюнкцию, и соединение. Вторая задача, которую мы уже выполнили, состоит в том, чтобы продемонстрировать, что конъюнкция может быть выражена в терминах отрицания и дизъюнкции. Соединение этих двух вещей вместе даст нам желаемый результат, что каждая возможная функция истинности можно выразить в терминах дизъюнкции и отрицания.На мы переходите к первой задаче.

Обычная форма

Хорошо, так что это ДИЗЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА мы упоминали? Ну, для того, чтобы дать четкое определение дизъюнктивной нормальной форме, нам сначала понадобится одна терминология:

Определение:

А ЛИТЕРАЛ любая формула сентенциальной логики, состоящей либо из сентенциальной письмо (т.грамм., П, Q, T и т. д.) или отрицательную сентенциальную букву (например, ¬П, ¬Q, ¬S и др.). Любая формула сентенциальной логики, содержащая тогда любая связка, кроме одиночного отрицания, является , а не литерал.

Хорошо, теперь, когда мы знаем, что такое литералы, мы можем перейти к определению дизъюнктивного нормального форма. Вот он:

Определение:

  • Формула сентенциальной логики находится в дизъюнктивной нормальности форма тогда и только тогда, когда она является одной из следующих:
    • буквальное
    • конъюнкция литералов
    • дизъюнкция литералов

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

ПРИМЕР:
  • п
  • ¬P
  • П и В
  • П против Q
  • P v (Q v R)
  • (P и Q) и ¬R
  • (P и Q) v ¬R
  • ((P & Q) & ¬R) v (R & ¬S)
  • ((P v Q) v R) v S

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

ПРИМЕР:
  • P & (Q против R)
  • P v ¬(Вопросы и ответы)
  • ¬(P v Q)
  • P v (Q & (R v T))

Итак, теперь мы знаем, что такое дизъюнктивное нормальные формы, нам нужно показать, что каждая возможная функция истинности может быть выражена формулой в дизъюнктивной нормальной форме.Хорошо сделать это, произведя АЛГОРИТМ , который позволит нам «перевести» таблицу истинности для конкретного функцию истинности в формулу в дизъюнктивной нормальной форме.

Во-первых, мы имеем дело с двумя особыми случаями: Две постоянные функции истинности, т. е. функция истинности которая всегда оказывается истинной, и функция истинности, которая всегда выходит ложно. На самом деле версий бесконечно много каждой функции, по одной на каждое возможное количество аргументов функция истинности может принимать.Однако это не проблема, поскольку мы можем выразить их все одними и теми же двумя формулами в дизъюнктивном нормальная форма. Формула постоянной «истинной» функции, независимо от количества аргументов, просто P v ¬P, а для постоянной «ложной» функции П и ¬П.

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

п Вопрос П → Q
Т Т Т
Т Ж Ж
Ф Т Т
Ф Ф Т

Наша цель здесь — создать формулу в дизъюнктивную нормальную форму, которая логически эквивалентна формула П → Q.Хотя мы уже знаем одну такую ​​формулу, а именно ¬P v Q — мы также хотим разработать процедуру определения эквивалентная формула в дизъюнктивной нормальной форме для любого функция истинности, а не только та, которая представлена ​​условным предложением. Не всякая возможная функция истинности будет иметь такой простой эквивалент, после всего.

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

Теперь каждый из этих дизъюнктов будет быть конъюнкцией литералов, верно? Верно. Теперь все, что нам нужно нужно определить, какие литералы, и мы готовы.Этот, однако это самая простая часть — все, что нам нужно сделать, это «скопировать» присвоение истинностного значения из этой строки следующим образом: Если в этом ряду стоит буква Т в предложении, то letter будет одним из наших литералов; если ему присваивается F, то отрицание этого сентенциального письма будет одним из наших литералы.

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

  • ((P и Q) v (¬P и Q)) v (¬P и ¬Q)

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

Итак, вот оно: процедура определения формула в дизъюнктивной нормальной форме, выражающая любую непостоянную функция истины. Учитывая нашу целевую функцию истинности, нам просто нужно «перевести» свою таблицу истинности, создав дизъюнкт для каждой строки, на которой задана функция истинности T, где каждое дизъюнктивное является конъюнкцией всех сентенциальных буквы, назначенные T в этой строке, и отрицания всех предложений буквы, назначенные F в этом ряду.

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

  • (¬(¬P v ¬Q) v ¬(P v ¬Q)) v ¬(P v Q)

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

Пока мы говорим о нормальных формах, есть одна последняя вещь, которую мы должны упомянуть — СОЮЗНАЯ НОРМАЛЬНАЯ ФОРМА .Конъюнктивная нормальная форма во многом похожа на дизъюнктивную. нормальная форма, только союзы и дизъюнкции перевернутый. Вот определение:

Определение:

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

Опять же, конечно, у нас есть понимание что дизъюнкт может содержать только один дизъюнкт, и что союз может содержать только один союз.

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

Универсал Штрихи

Итак, теперь, когда мы доказали, что логика истинно функционально полна, что всякая формула сентенциальная логика эквивалентна формуле в (либо конъюнктивном или дизъюнктивная) нормальная форма, и что комбинация дизъюнкции а отрицание есть истинностно-функционально полный набор связок, есть только один последний вопрос об истинностно-функциональной полноте что необходимо решить — есть ли единственная связка, которая сам по себе представляет собой истинно-функционально полный комплект? Фактически, есть.Это называется инсультом Шеффера, и обычно представлен символом ↑. Это его характеристика таблица истинности:

п Вопрос П ↑ Q
Т Т Ф
Т Ф Т
Ф Т Т
Ф Ф Т

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

Итак, как выразить унарную связку с точки зрения бинарника? Просто: используя ту же формулу дважды:

Довольно об отрицании, как насчет дизъюнкции? Давайте все обдумаем. Мы знаем, что дизъюнкция может быть определена с точки зрения отрицания и союза, благодаря ДеМоргану законы. Мы уже знаем, как определить отрицание в терминах Инсульт Шеффера, поэтому давайте посмотрим на определение дизъюнкции. с точки зрения отрицания и союза для подсказок.Мы знаем это P v Q эквивалентно ¬(¬P & ¬Q), что можно «перевести» на английский язык следующим образом: Не оба не- П и не- В. Хорошо, если мы посмотрим на таблицу истинности, П ↑ Q ложно как раз в оба случая Р и Q верны, поэтому, если мы рассмотрим ¬P ↑ ¬Q, то это быть ложным на всякий случай ¬P и ¬Q верны, а это именно то, что нам нужно.Ввод этого все вместе получаем — ну разберетесь, потом проверите таблицу истинности ниже, чтобы убедиться, что вы все поняли правильно.

Вот таблица истинности:

п п П ↑ П Q ↑ Q П против Q
Т Т Ж Т Ж Т
Т Ж Ж Т Т Т
Ф Т Т Т Ф Т
Ж Ж Т Ж Т Ж

Вот и все.Инсульт Шеффера (также известный как НАНД — что коротко для не и —оператор очевидного разум) сам по себе является истинно функционально полным набором связок.

На самом деле, инсульт Шеффера не единственный связка, которая сама по себе является истинно-функционально законченной задавать. Есть еще один инсульт, известный как инсульт Пирса (или в NOR ), который также подходит под это описание.

Вот таблица истинности:

п Вопрос П ↓ Q
Т Т Ф
Т Ж Ж
Ж Т Ж
Ф Ф Т

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

Упражнения

Упражнение: 8.1

Какие из следующих логически эквивалентны к (P и Q) → R?

  1. R v ¬(P и Q)
  2. P & (¬¬Q & ¬R)
  3. П → (Q → R)
  4. П → (Вопросы и ответы)
  5. (R v ¬P) v ¬Q

Упражнение: 8.2

Что из следующего является логическим следствием из (J и K) и (L v ¬M)?

  1. Джей и К
  2. J v ¬M
  3. J & ¬M
  4. К → Л
  5. М → Л

Упражнение: 8.3

Какие из следующих формул являются литералами?

  1. А и Б
  2. ¬B
  3. А
  4. Б → А
  5. А v ¬А
  6. ¬A
  7. Б
  8. Б ↔ А
  9. А ↔ ¬В
  10. Б против А

Упражнение: 8.4

Какие из следующих формул являются дизъюнктивными нормальная форма?

  1. П и В
  2. П → (Вопросы и ответы)
  3. Р в П
  4. Q v (P и ¬R)
  5. (P и ¬R) и Q
  6. Q v (P v R)
  7. ¬P
  8. ¬(P v Q)
  9. ¬P v (Вопросы и ответы)
  10. P v (¬Q v ¬R)

Упражнение: 8.5

Какие из следующих формул находятся в конъюнктиве нормальная форма?

  1. П против Q
  2. П и В
  3. P v ¬Q
  4. P → (Q и ¬R)
  5. R & (P v ¬R)
  6. ¬Q v (P v R)
  7. ¬P и ¬R
  8. (P и Q) против R
  9. (P против Q) & R
  10. (P v ¬Q) и (R v Q)

Упражнение: 8.6

Завершите каждое из следующих производных:

и
Производное: (¬P v ¬Q) ↔ ¬(P и Q)
Попробуйте в CPL:
II
Производное: (P → Q) ↔ (¬P v Q)
Попробуйте в CPL:
iii
Производное: Л
1. М ↔ Л Прем
2. П ↔ М Прем
3. п Прем
Попробуйте в CPL:
IV
Производное: Вопросы и ответы
1. R&A Прем
2. Р ↔ Q Прем
Попробуйте в CPL:
против
Производное: (A ↔ B) ↔ ((A и B) v ¬(A v B))
Попробуйте в CPL:
ви
Производное: Д ↔ Е
1. Д → А Прем
2. А → Е Прем
3. ¬E v D Прем
Попробуйте в CPL:
vii
Производное: H v ¬(P и Q)
1. ¬G Прем
2. G ↔ (P и Q) Прем
Попробуйте в CPL:
viii
Производное: А ↔ (S v T)
1. А → С Прем
2. Т → (П и ¬П) Прем
Попробуйте в CPL:
ix
Производное: К
1. (К ↔ ¬М) и ¬М Прем
Попробуйте в CPL:
х
Производное: (F v G) ↔ ¬(¬F и ¬G)
Попробуйте в CPL:

Экзамен

PPT — Раздел 3.2: Таблицы истинности для отрицания, конъюнкции и дизъюнкции Презентация PowerPoint

  • Раздел 3.2: Таблицы истинности для отрицания, конъюнкции и Математика дизъюнкции 121

  • Таблицы истинности Таблица истинности используется для определения составной таблицы утверждение истинно или ложно. Они используются для разбиения сложного составного оператора на простые, более понятные части.

  • Таблица истинности для отрицания Как видите, «P» является истинным утверждением, тогда его отрицание «~P» или «не P» ложно.Если «P» ложно, то «~P» истинно. P ~PTFFT

  • Четыре возможных случая Когда составное утверждение включает два простых утверждения P и Q, возможны четыре случая для объединенных значений истинности P и Q. TTTFTFFF

  • Когда соединение истинно ? Предположим, я скажу классу: «Вы можете пересдать последний экзамен и сдать эту лабораторную позже». Пусть P будет «Вы можете пересдать последний экзамен», а Q будет «Вы можете сдать эту лабораторную позже.Какие значения истинности для P и Q позволяют мне сдержать свое обещание P Λ Q классу?

  • Когда союз верен? продолжение П: «Вы можете пересдать последний экзамен». В: «Вы можете сдать эту лабораторию поздно». Есть четыре возможности. 1. P истинно и Q истинно, то P Λ Q истинно. 2. P истинно и Q ложно, то P Λ Q ложно. 3. P ложно и Q истинно, то P Λ Q ложно. 4. P ложно и Q ложно, то P Λ Q ложно.

  • Таблица истинности для соединения P ΛQ T T T F T F T F F F F F

  • 3.2 Вопрос 1 Каково истинное значение утверждения «Университет М находится в Анн-Арборе, а Энн-Арбор — в Западной Вирджинии»? 1. Верно 2. Ложно

  • Когда дизъюнкция истинна? Предположим, я сообщаю классу, что за этот модуль вы получите полный балл, если «Вы сделаете контрольную домашнюю работу или выполните лабораторную работу». Пусть P будет утверждением «Вы выполняете домашнее задание», а пусть Q будет утверждением «Вы выполните лабораторную работу». Для каких значений истинности P и Q я бы сказал, что вы сделали то, что я сказал, что является PVQ, чтобы получить полную оценку за эту единицу?

  • Когда истинна дизъюнкция? продолжение П: «Вы выполняете домашнее задание». Вопрос: «Вы делаете лабораторию». Есть четыре возможности: 1. P истинно и Q истинно, тогда P V Q истинно. 2. P истинно и Q ложно, тогда P V Q истинно. 3. P ложно и Q истинно, тогда P V Q истинно. 4. P ложно и Q ложно, тогда P V Q ложно.

  • Таблица истинности для дизъюнкции P V Q T T T T T F T F T F F F

  • 3.2 Вопрос 2 Каково истинное значение утверждения «WVU находится в Аризоне или Вирджиния Моргантаун» находится в Западной части? 1.Истина 2. Ложь

  • Сводка таблицы истинности Вы можете запомнить таблицы истинности для ~(не), Λ(и), и, V(или), запомнив следующее: ~(не) — значение истинности всегда противоположное Λ(и) — всегда ложно, за исключением случаев, когда оба истинны V (или) — всегда истинны, кроме случаев, когда оба ложны

  • Составление таблицы истинности Пример ОДИН или V простых утверждений P и Q и, возможно, отрицание простых утверждений ~P и ~Q.Например, составим таблицу истинности для утверждения ~PVQ

  • . Λ ~QPQPTTTFFTFTTTFTFFFFF FTF Столбец окончательного ответа То же, что и в столбце 1 Напротив столбца 2

  • 3.2 Вопрос 3 Какой столбец ответа в таблице истинности утверждения ~P Λ ~Q ? 1.T 2. T 3. FF FFFTFFFT

  • ~P Λ~Q Λ ~QPQ ~PTTFFFFTFFFTFTTFFFFTTT Итоговый столбец ответа Напротив столбца 1 Напротив столбца 2

  • 7 Таблица

    таблица истинности для более сложного утверждения, (PV~Q) V (~PΛQ) Мы составим таблицу истинности, как и раньше.Наш окончательный ответ будет находиться под самой доминирующей связкой, не заключенной в круглые скобки (тот, что в середине)

  • Более сложные таблицы истинности TTTFFTFTTTFFFTTFTTTFF TTTFFTF Окончательный ответ Напротив столбца 1 Напротив столбца 2 То же, что и в столбце 1, И то же, что и в столбце 2 ИЛИ

  • Более сложные таблицы истинности Теперь составим таблицу истинности для (PV~Q) Λ(~P Λ Q) Каждое из утверждений в скобках ( PV~Q) и (~P Λ Q) точно такое же, как утверждения мы сделали ранее, поэтому мы заполняем их таблицы истинности, как мы только что сделали.

  • Более сложные таблицы истинности. содержали только два простых утверждения (P и Q) с четырьмя вариантами истинно-ложно.

  • Построение таблиц истинности с тремя простыми утверждениями продолжение.Когда составное утверждение состоит из трех простых утверждений (P, Q и R), теперь существует восемь возможных комбинаций «истина-ложь».

  • Построение таблиц истинности с тремя простыми утверждениями прод.

  • Пример с тремя утверждениями Пусть s построит таблицу истинности для утверждения (PV Q) Λ ~R, используя те же методы, что и раньше.

  • Пример с тремя утверждениями TTTTFFFF TTTTTTFF TTFFTTFF FTFTFTFF FTFTFTFT

  • Практика • Определите значение истинности для утверждения IF: ~ PV: • P истинно, Q ложно и R ) Λ (~RV ~ P)

  • Практика • Перевести в символы.

  • alexxlab

    Добавить комментарий

    Ваш адрес email не будет опубликован.