Дискретная математика - логика высказываний

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

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

Предложная логика - определение

Предложение - это набор декларативных утверждений, которые имеют либо значение истинности «истина», либо значение истинности «ложь». Пропозициональное выражение состоит из пропозициональных переменных и связок. Мы обозначаем пропозициональные переменные заглавными буквами (A, B и т. Связки соединяют пропозициональные переменные.

Некоторые примеры предложений приведены ниже -

• «Человек смертен», возвращает истинное значение «ИСТИНА».
• «12 + 9 = 3–2», возвращает истинное значение «FALSE».

Следующее не является предложением -

• «А меньше 2». Это потому, что, если мы не дадим конкретное значение A, мы не сможем сказать, истинно это утверждение или нет.

Соединительные

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

• ИЛИ ($ \ lor $)

• И ($ \ земля $)

• Отрицание / НЕ ($ \ lnot $)

• Следствие / если-то ($ \ rightarrow $)

• Если и только если ($ \ Leftrightarrow $).

OR ($\lor$) - Операция ИЛИ двух предложений A и B (записываемых как $ A \ lor B $) истинна, если по крайней мере любая из пропозициональных переменных A или B истинна.

Таблица истинности выглядит следующим образом -

А	B	А ∨ Б
Правда	Правда	Правда
Правда	Ложь	Правда
Ложь	Правда	Правда
Ложь	Ложь	Ложь

AND ($\land$) - Операция AND двух предложений A и B (записываемых как $ A \ land B $) истинна, если истинны обе пропозициональные переменные A и B.

Таблица истинности выглядит следующим образом -

А	B	А ∧ Б
Правда	Правда	Правда
Правда	Ложь	Ложь
Ложь	Правда	Ложь
Ложь	Ложь	Ложь

Negation ($\lnot$) - Отрицание предложения A (записывается как $ \ lnot A $) ложно, когда A истинно, и истинно, когда A ложно.

Таблица истинности выглядит следующим образом -

А	¬ А
Правда	Ложь
Ложь	Правда

Implication / if-then ($\rightarrow$)- Импликация $ A \ rightarrow B $ - это предложение «если A, то B». Это ложь, если A истинно, а B ложно. Остальные случаи верны.

Таблица истинности выглядит следующим образом -

А	B	А → Б
Правда	Правда	Правда
Правда	Ложь	Ложь
Ложь	Правда	Правда
Ложь	Ложь	Правда

If and only if ($ \Leftrightarrow $) - $ A \ Leftrightarrow B $ - это двухусловная логическая связка, которая истинна, когда p и q одинаковы, т.е. оба ложны или оба истинны.

Таблица истинности выглядит следующим образом -

А	B	А ⇔ Б
Правда	Правда	Правда
Правда	Ложь	Ложь
Ложь	Правда	Ложь
Ложь	Ложь	Правда

Тавтологии

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

Example - Докажите, что $ \ lbrack (A \ rightarrow B) \ land A \ rbrack \ rightarrow B $ является тавтологией

Таблица истинности выглядит следующим образом -

А	B	А → Б	(А → В) ∧ А	[(A → B) ∧ A] → B
Правда	Правда	Правда	Правда	Правда
Правда	Ложь	Ложь	Ложь	Правда
Ложь	Правда	Правда	Ложь	Правда
Ложь	Ложь	Правда	Ложь	Правда

Как мы видим, каждое значение $ \ lbrack (A \ rightarrow B) \ land A \ rbrack \ rightarrow B $ "Истинно", это тавтология.

Противоречия

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

Example - Докажите, что $ (A \ lor B) \ land \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $; противоречие.

Таблица истинности выглядит следующим образом -

А	B	А ∨ Б	¬ А	¬ B	(¬ A) ∧ (¬ B)	(A ∨ B) ∧ [(¬ A) ∧ (¬ B)]
Правда	Правда	Правда	Ложь	Ложь	Ложь	Ложь
Правда	Ложь	Правда	Ложь	Правда	Ложь	Ложь
Ложь	Правда	Правда	Правда	Ложь	Ложь	Ложь
Ложь	Ложь	Ложь	Правда	Правда	Правда	Ложь

Как мы видим, каждое значение $ (A \ lor B) \ land \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ является «ложным», противоречие.

Непредвиденные обстоятельства

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

Example - Докажите, что $ (A \ lor B) \ land (\ lnot A) $ случайное обстоятельство.

Таблица истинности выглядит следующим образом -

А	B	А ∨ Б	¬ А	(A ∨ B) ∧ (¬ A)
Правда	Правда	Правда	Ложь	Ложь
Правда	Ложь	Правда	Ложь	Ложь
Ложь	Правда	Правда	Правда	Правда
Ложь	Ложь	Ложь	Правда	Ложь

Как мы видим, каждое значение $ (A \ lor B) \ land (\ lnot A) $ имеет как «Истина», так и «Ложь», это случайность.

Пропозициональные эквивалентности

Два утверждения X и Y логически эквивалентны, если выполняется любое из следующих двух условий:

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

• Двуусловное утверждение $ X \ Leftrightarrow Y $ является тавтологией.

Example - Докажите, что $ \ lnot (A \ lor B) и \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ эквивалентны

Тестирование 1- ^м методом (Таблица истинности соответствия)

А	B	А ∨ Б	¬ (A ∨ B)	¬ А	¬ B	[(¬ A) ∧ (¬ B)]
Правда	Правда	Правда	Ложь	Ложь	Ложь	Ложь
Правда	Ложь	Правда	Ложь	Ложь	Правда	Ложь
Ложь	Правда	Правда	Ложь	Правда	Ложь	Ложь
Ложь	Ложь	Ложь	Правда	Правда	Правда	Правда

Здесь мы можем видеть, что значения истинности $ \ lnot (A \ lor B) и \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ совпадают, следовательно, утверждения эквивалентны.

Тестирование по 2- ^му методу (Двухусловность)

А	B	¬ (A ∨ B)	[(¬ A) ∧ (¬ B)]	[¬ (A ∨ B)] ⇔ [(¬ A) ∧ (¬ B)]
Правда	Правда	Ложь	Ложь	Правда
Правда	Ложь	Ложь	Ложь	Правда
Ложь	Правда	Ложь	Ложь	Правда
Ложь	Ложь	Правда	Правда	Правда

Поскольку $ \ lbrack \ lnot (A \ lor B) \ rbrack \ Leftrightarrow \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ является тавтологией, утверждения эквивалентны.

Обратный, обратный и контрположительный

Импликация / if-then $ (\ rightarrow) $ также называется условным выражением. Он состоит из двух частей -

• Гипотеза, стр.
• Заключение, q

Как упоминалось ранее, он обозначается как $ p \ rightarrow q $.

Example of Conditional Statement- «Если вы сделаете домашнее задание, вас не накажут». Здесь «вы делаете домашнее задание» - это гипотеза, p, а «вы не будете наказаны» - это заключение, q.

Inverse- Инверсия условного утверждения - это отрицание как гипотезы, так и вывода. Если утверждение - «Если p, то q», обратным будет «Если не p, то не q». Таким образом, обратное к $ p \ rightarrow q $ - это $ \ lnot p \ rightarrow \ lnot q $.

Example - Обратное выражение «Если ты сделаешь домашнее задание, тебя не накажут» - это «Если ты не сделаешь домашнее задание, тебя накажут».

Converse- Обратное условное утверждение вычисляется путем замены гипотезы и заключения. Если утверждение: «Если p, то q», обратное будет «Если q, то p». Обратное к $ p \ rightarrow q $ - это $ q \ rightarrow p $.

Example - Обратное выражение «Если ты делаешь домашнее задание, ты не будешь наказан»: «Если ты не будешь наказан, ты делаешь свое домашнее задание».

Contra-positive- Противоположное положительное для условного выражения вычисляется путем замены гипотезы и заключения обратного утверждения. Если утверждение - «Если p, то q», то противоположным положительным ответом будет «Если не q, то не p». Контрпозитив $ p \ rightarrow q $ равен $ \ lnot q \ rightarrow \ lnot p $.

Example - Противоположным положением «Если ты сделаешь домашнее задание, ты не будешь наказан», это «Если тебя наказали, ты не сделал домашнее задание».

Принцип двойственности

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

Example - Двойственным к $ (A \ cap B) \ cup C $ является $ (A \ cup B) \ cap C $

Нормальные формы

Мы можем преобразовать любое предложение в две нормальные формы -

• Конъюнктивная нормальная форма
• Дизъюнктивная нормальная форма

Конъюнктивная нормальная форма

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

Examples

• $ (A \ lor B) \ земля (A \ lor C) \ land (B \ lor C \ lor D) $

• $ (P \ чашка Q) \ cap (Q \ чашка R) $

Дизъюнктивная нормальная форма

Составной оператор находится в дизъюнктивной нормальной форме, если он получен операцией ИЛИ между переменными (включая отрицание переменных), связанными с И. С точки зрения операций над множествами, это составной оператор, полученный с помощью Union среди переменных, связанных с Intersections.

Examples

• $ (A \ земля B) \ lor (A \ земля C) \ lor (B \ земля C \ земля D) $

• $ (P \ cap Q) \ чашка (Q \ cap R) $