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

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

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

Предлогическая логика — определение

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

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

• «Человек — смертный», он возвращает истинное значение «ИСТИНА»
• «12 + 9 = 3 — 2», возвращает значение истинности «ЛОЖЬ»

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

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

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

Связки

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

• ИЛИ ($\ lor$)

• AND ($\ land$)

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

• Импликация / если-тогда ($\ rightarrow$)

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

ИЛИ ($\ lor$)

AND ($\ land$)

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

Импликация / если-тогда ($\ rightarrow$)

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

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

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

	В	A ∨ B
Правда	Правда	Правда
Правда	Ложь	Правда
Ложь	Правда	Правда
Ложь	Ложь	Ложь

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

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

	В	A ∧ B
Правда	Правда	Правда
Правда	Ложь	Ложь
Ложь	Правда	Ложь
Ложь	Ложь	Ложь

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

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

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

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

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

	В	A → B
Правда	Правда	Правда
Правда	Ложь	Ложь
Ложь	Правда	Правда
Ложь	Ложь	Правда

Если и только если ($\ Leftrightarrow$) — $A \ Leftrightarrow B$ — это двухусловное логическое связующее, которое истинно, когда p и q одинаковы, т.е. оба являются ложными или оба истинны.

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

	В	A ⇔ B
Правда	Правда	Правда
Правда	Ложь	Ложь
Ложь	Правда	Ложь
Ложь	Ложь	Правда

Тавтологии

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

Пример — Доказать, что $\ lbrack (A \ rightarrow B) \ land A \ rbrack \ rightarrow B$ — тавтология

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

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

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

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

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

Пример — Докажите, что $(A \ lor B) \ land \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack$ является противоречием

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

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

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

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

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

Пример — Доказать непредвиденную случайность в $(A \ lor B) \ land (\ lnot A)$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

	В	¬ (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)$ также называется условным оператором. Он состоит из двух частей —

• Гипотеза, р
• Вывод, д

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

Пример условного высказывания — «Если вы делаете свою домашнюю работу, вы не будете наказаны». Здесь «вы делаете свою домашнюю работу» — это гипотеза, p, а «вы не будете наказаны» — это заключение, q.

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

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

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

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

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

Пример — Противоположный вариант «Если вы делаете домашнее задание, вы не будете наказаны» — «Если вы наказаны, вы не сделали домашнее задание».

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

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

Пример — двойственное значение $(A \ cap B) \ cup C$ равно $(A \ cup B) \ cap C$

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

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

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

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

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

Примеры

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

• $(P \ cup Q) \ cap (Q \ cup R)$

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

$(P \ cup Q) \ cap (Q \ cup R)$

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

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

Примеры

$(A \ land B) \ lor (A \ land C) \ lor (B \ land C \ land D)$

$(P \ cap Q) \ cup (Q \ cap R)$