Алгебра логики высказываний

Алгебра логики высказываний

Основные понятия

 

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

Обычно  элементарные высказывания обозначают строчными буквами латинского алфавита a, b, c, x, y …, которые также являются логическими переменными. Истинные значения обозначаются буквой И или 1, а ложные – Л или 0.

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

Х	у	Øх	х Ù  у	х Ú  у	х ®  у	х  º  у
0	0	1	0	0	1	1
0	1	1	0	1	1	0
1	0	0	0	1	0	0
1	1	0	1	1	1	1

Связки имеют следующий приоритет: Ø Ù Ú ® º. Приоритет операций, представленных логическими связками можно изменить с помощью скобок. Высказывания, построенные с помощью простых высказываний, связок и скобок, называют правильно построенными формулами или сокращённо формулами.

Замечательным свойством логики высказываний является то, что ее семантика близка к соответствующим высказываниям  на естественном языке. Так, например семантика формул содержащих связки Ø и Ù практически совпадает со смыслом фраз содержащих слова «не» и «и». Однако имеются и некоторые различия. Так формула х Ú у несколько шире, чем русское «х или у». Выражение «х или у» по смыслу ближе к формуле х Ù Øу Ú Øх Ù у. Еще больше различий между семантикой формулы х ® у в логике высказываний и выражению «из х следует у». В русском языке это выражение истинно, если истинны х и у, т.е. предложение русского языка по смыслу совпадает с формулой х Ù у. Логическое следствие истинно также, если х и у ложны или х ложна, а у истинна. Логическую формулу х ® у следует интерпретировать на естественном языке так: «Если х истинна, то у тоже истинна, а остальное неизвестно».

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

х	у	Ø х	Ø x Ú у	Ø х Ù (Ø x Ú  у)	Ø x Ù (Ø x Ú у) ® Ø x
0	0	1	1	1	1
0	1	1	1	1	1
1	0	0	0	0	1
1	1	0	0	0	1

Очевидно, что если формула содержит n переменных, то в таблице истинности будет содержаться 2ⁿ строк. В приведенном примере формула содержит 2 переменные и 2² = 4 строки. Кроме того, данная формула истинна на любом наборе значений своих переменных. Такие формулы называются тождественно истинными или тавтологиями. В противоположной ситуации, формула является тождественно ложной или невыполнимой. Если две разные формулы принимают одинаковые значения на любом наборе значений переменных, то такие формулы называют равносильными. Равносильные формулы будем обозначать знаком равенства =.

Законы алгебры логики

 

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

• законы идемпотентности:
• x Ù x = x
• x Ú x = x
• x Ù 1 = x
• x Ú 1 = 1
• x Ù 0 = 0
• x Ú 0 = x
• x Ù Ø x = 0 – закон противоречия
• x Ú Ø x = 1 – закон исключения третьего
• Ø Ø x = x – закон снятия двойного отрицания
• законы поглощения
• x Ù (y Ú x) = x
• x Ú (y Ù x) = x

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

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

• (x º y) = (x ® y) Ù (y ® x)
• x ® y = Ø x Ú y
• законы Де Моргана
• Ø (y Ú x) = Ø y Ù Ø x
• Ø (y Ù x) = Ø y Ú Ø x

Замечательным следствием приведенных  выше законов является следующий факт. Любую логическую формулу можно заменить равносильной ей, но содержащую только две логические операции: конъюнкцию или отрицание или дизъюнкцию или отрицание. Дальнейшее исключение логических операций, очевидно, невозможно, то есть приведенные пары представляют минимальный базис для построения правильно построенных формул. Однако существует операция, с помощью которой можно представить любую логическую связку. Эта операция получила название «штрих Шеффера» и определяется следующим образом:

х	у	х | у
0	0	1
0	1	1
1	0	1
1	1	0

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

• Ø x =  x | x
• x Ù y = (x | y) | (x | y)

Также следует отметить, что x | y = Ø (x Ù y).

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

• коммутативные законы
• х Ù y = y Ù х
• х Ú y = y Ú х
• дистрибутивные законы
• х Ù (y Ú z) = (х Ù y) Ú (х Ù z)
• х Ú (y Ù z) = (х Ú y) Ù (х Ú z)
• ассоциативные законы
• х Ù (y Ù z) = (х Ù y) Ù z
• х Ú (y Ú z) = (х Ú y) Ú z

Еще одним важным законом алгебры  логики является закон двойственности. Пусть формула A содержит только операции конъюнкции, дизъюнкции и отрицания. Для операции конъюнкции двойственной считается дизъюнкция, а для дизъюнкции – конъюнкция. Тогда по определению формулы A и A* называются двойственными, если формула A* получается из A путем замены в ней каждой операции на двойственную. Например, для формулы (х Ú y) Ù z двойственной формулой будет (х Ù y) Ú z. Для двойственных формул справедлива следующая теорема: если формулы A и B равносильны, то равносильны и двойственные им формулы, то есть A* = B*. Данную теорему оставим без доказательства.

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

Под сложностью формул обычно понимается количество символов, используемых для  ее записи. То есть формула α проще  формулы b, если α содержит меньше букв и логических операций. Например, для формулы (Ø (x Ú y) ® x Ú y) Ù y можно записать следующую цепочку преобразований, приводящих ее к более простому виду:

(ØØ (x Ú y) Ú x Ú y) Ù y = (x Ú y Ú x Ú y) Ù y = (x Ú y) Ù y = y.

Функции алгебры логики

 

Значение формулы алгебры логики полностью зависит от значений входящих в нее высказываний. Поэтому такая формула может считаться функцией входящих в нее элементарных высказываний. Например, (x Ù y) ® Ø z является функцией f(x, y, z). Естественно, значения этой функции и входящих в нее элементов могут принимать значения истина или ложь. Тождественно истинные или тождественно ложные функции представляют собой константы.

Каждую функцию алгебры логики можно записать в виде формулы или представить таблицей истинности. Как уже было отмечено выше, таблица истинности для n переменных содержит 2ⁿ строк. Следовательно, каждая функция алгебры логики принимает 2ⁿ значений, состоящих из 0 или 1. Общее же число наборов значений, состоящих из 0 и 1, длины 2ⁿ равно 2²ⁿ. В частности, число различных функций от одной переменной равно четырем.

х	f1(x)	f2(x)	f3(x)	F4(x)
0	1	1	0	0
1	1	0	1	0

Из этой таблицы следует, что  две функции являются константами f₁(x) = 1 и – f₂(x) = x, а остальные f₃(x) = Ø x и f₄(x) = 0.

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

 

Пусть с помощью таблицы истинности задана произвольная функция алгебры  логики n переменных F(x₁, x₂, …, x_n). Рассмотрим формулу:

   F(1, 1, …, 1) Ù x₁ Ù x₂ Ù … Ù x_n Ú

Ú F(1, 1, …, 1, 0) Ù x₁ Ù x₂ Ù … Ù x_n-1 Ù Ø x_n Ú                                         (1)

Ú F(1, 1, …, 0, 1) Ù x₁ Ù x₂ Ù … Ù Ø x_n-1 Ù x_n Ú

Ú F(0, 0, …, 0) Ù Ø x₁ Ù Ø x₂ Ù … Ù Ø x_n

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

Ясно, что формула (1) полностью  определяет функцию F. Иначе говоря, значения функции F и формулы (1) совпадают на всех наборах значений переменных x_i. Например, если x₁ принимает значение 0, а остальные переменные принимают значение 1, то функция F принимает значение F(0, 1, 1, …, 1). При этом логическое слагаемое F(0, 1, …, 1) Ù Ø x₁ Ù x₂ Ù … Ù x_n = F(0, 1, …, 1) Ù Ø 0 Ù 1 Ù … Ù 1, входящее в формулу (1), принимает также значение F(0, l,..., l), а все остальные логические слагаемые формулы (1) имеют значение 0. Действительно, в них знаки отрицания перед переменными распределяются иначе, чем в рассмотренном слагаемом. Таким образом, при подстановке вместо переменных тех же значений в конъюнкцию войдет символ 0 без знака отрицания, а символ 1 под знаком отрицания. В таком случае один из членов конъюнкции будет иметь значение 0, и поэтому вся конъюнкция также будет иметь значение 0. В связи с этим на основании закона x Ú 0 = x значением формулы (1) является F(0, l,..., l).

Ясно, что вид формулы (1) может быть значительно упрощен, если в ней отбросить те логические слагаемые, в которых первый член конъюнкции имеет значение 0 (и, следовательно, вся конъюнкция имеет значение 0). Если же в логическом слагаемом первый член конъюнкции (то есть определенное значение функции F) имеет значение 1, то, пользуясь законом 1 Ù х = x, этот член конъюнкции можно не выписывать.

Таким образом, в результате получается формула (1), которая содержит только элементарные переменные высказывания и обладает следующими свойствами:

• каждое логическое слагаемое формулы содержит все переменные, входящие в функцию F(x₁, x₂, …, x_n),
• все логические слагаемые формулы различны,
• ни одно логическое слагаемое формулы не содержит одновременно переменную и ее отрицание,
• ни одно логическое слагаемое формулы не содержит одну и ту же переменную дважды,

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

Если функция F(x₁, x₂, …, x_n) задана таблицей истинности, то соответствующая ей формула алгебры логики может быть получена просто. Действительно, для каждого набора значений переменных, на котором функция F(x₁, x₂, …, x_n) принимает значение 1, записывается конъюнкция элементарных переменных высказываний, взяв за член конъюнкции х_k, если значение x_k на указанном наборе значений переменных функции F есть 1 и Ø х, если значение x_k есть 0. Дизъюнкция всех записанных конъюнкций и будет искомой формулой.