Дисциплина: ЭВМ и периферийные устройства НОУ ВО Московский технологический

Александр Валерьевич
Математическая логика

(Булева алгебра)

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

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


Льюис Кэрролл
(псевдоним Чарльза Лютвиджа Доджсона
(1832–1898))
известный английский математик и литератор

заложены ещё в работах Аристотеля в 384 г. до н.э.
Достижения

Аристотеля в области логики не претерпели существенных изменений вплоть до XVII века. Впервые идеи обоснования логики на основе вычислений, подобно тому как мы оперируем символами в алгебре, были высказаны ещё в XVII веке Готфридом Лейбницем. Идеи Лейбница реализовал в своих работах английский математик Джордж Буль (1815 – 1864). В 1847 г. он опубликовал работу "Математический анализ логики", в которой высказал идею, что логика более близка к математике, чем к философии.

развивающихся разделов математики – математической логики.

Математическая логика применяется в информатике,

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

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

Алгебра натуральных чисел: элементы алгебры – натуральные числа, а операции – сложение и умножение

Векторная алгебра изучает действия с направленными отрезками (векторами).

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

Простое высказывание - повествовательное предложение, в котором

говорится об одном-единственном событии.
Например, предложение «Луна – спутник Земли» есть простое высказывание, предложение «Не сорить!» не является высказыванием.

Высказывания обозначаются большими буквами латинского алфавита. Если высказывание A истинно, то пишут A = 1, если ложно, то используют запись A = 0.

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

высказываний в одно при помощи союза «И».
Связка «И» называется конъюнкцией

высказываний A и B и принимает значений истина, только когда оба высказывания истинны, в других случаях конъюнкция принимает значение ложь.
Обозначают конъюнкцию суждений A и B как A&B, A and B (в программировании), A Λ B (в учебниках по логике).

Например:
высказывание A – «В лесу растут грибы»,
высказывание B – «Льюис Кэрролл – математик»,
составим произведение этих высказываний
AB – «В лесу растут грибы и Льюис Кэрролл – математик».

Истинность произведения высказываний зависит от истинности перемножаемых высказываний и может быть определена с помощью следующей таблицы:

перемножаемых высказываний и может быть определена с помощью следующей таблицы:

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

смысле.

Логически связка «ИЛИ» называется дизъюнкцией. Дизъюнкция двух высказываний А и В принимает значение «истина», если хотя бы одно из высказываний истинно, и значение «ложь», если оба высказывания ложны.
Для дизъюнкции используют обозначение A+B, в программировании используют обозначение A or B, в учебниках по логике A V B.

Например: высказывание
A – «Декабрь – зимний месяц»,
В – «Летом иногда идет дождь»,
определим высказывание A+B – «Декабрь – зимний месяц или летом иногда идет дождь».

помощью следующей таблицы:

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

связки «или А, или В». Она носит исключающий характер, т.к. принимает значение истина, когда операнды имеют разное логическое значение. Обозначается в программировании как A xor B; таблица истинности имеет вид:

высказываний «если A, то В» принимает значение ложь только в

одном случае, когда А истинно, а В ложно. Импликация обозначается как A→B. Суждение А называется посылкой, В следствием.

Иногда употребляются термины антецедент для посылки А и консеквент – для заключения В.

словами «А тогда и только тогда, когда В», «для А

необходимо и достаточно В».

Эквиваленция обозначается как А↔В и выражается через импликацию и конъюнкцию:

А↔В = (А→В) Λ (B→A)

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

высказыванием.

Выполнить операцию логического отрицания (обозначается Ā) – значит получить из

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

Истинность высказывания Ā определяется таблицей:

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

выполнения логических действий можно использовать круглые скобки.
Для однозначного прочтения логических выражений принят следующий приоритет выполнения операций (перечислены в порядке убывания приоритета):
отрицание (самая «сильная» операция),
конъюнкция,
дизъюнкция,
сильная дизъюнкция,
импликация,
эквиваленция.
Например,
А Λ В V С = (А Λ В) V С; Ā V В → С = (( Ā ) V В) → С

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

которых либо одни единицы, либо только нули. Это означает, что

высказывание либо всегда истинно, либо ложно, независимо от истинности входящих в него высказываний.

Например: высказывание всегда истинно А + Ā, а высказывание всегда ложно АĀ. Доказать это можно составив таблицу истинности этих высказываний.

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

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

Тождественно истинные или тождественно ложные высказывания, если они встречаются в формулах, заменяются в них, соответственно единицей или нулем:

являются, например, высказывания и
Ā

+ В (то есть ). Это можно проверить составив таблицы истинности этих высказываний:

обладают следующими важными свойствами:
Отрицание:
Формулы называются формулами Августа де Моргана

(1806–1871). Используя эти формулы, можно, в частности, преобразовывать высказывания: сложные заменять более простыми.

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

обладают специфическими свойствами

A + A = A, AA = A, A + 1 = A.

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

(A + B)(A + C) = AA + AC + AB + BC = A + AB + AC + BC.

Рассмотрим теперь два первых слагаемых

A + AB = A(1 + B) = A1 = A и аналогично A+ AC = A.

Таким образом, окончательно получаем (A + B)(A + C) = A+ BC.

Преобразование A + AB = A очень часто встречается в алгебре высказываний и называется «поглощение».

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

Суть его состоит

в следующем:
(склеивание произошло по символу B). Соответственно для сложного высказывания склейку можно произвести по символу С, то есть имеет место тождественное преобразование .

к решению логических задач

Например:

Задача:

Алеша, Боря и Гриша откопали древний сосуд. О том, где и когда он был изготовлен, каждый из школьников высказал по два предположения:

Алеша: «Это сосуд греческий и сосуд изготовлен в V веке»;

Боря: «Это сосуд финикийский и сосуд изготовлен в III веке»;

Гриша: «Это не греческий сосуд и изготовлен он в IV веке».

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

греческий» – G ;

«Это сосуд финикийский» – F;

«Сосуд

изготовлен в V веке» – 5;

«Сосуд изготовлен в III веке» – 3;

«Сосуд изготовлен в IV веке» – 4.

с учетом высказывания учителя.

Формула Алешиного высказывания имеет вид G5. Учитель

сказал, что Алеша прав только в одном из своих утверждений, поэтому либо G = 1, либо 5 = 1. Истинным будет высказывание
, то есть высказывание «Сосуд греческий и изготовлен не в 5 веке или сосуд не греческий и изготовлен в 5 веке».

Аналогично, высказывание Бори можно представить формулой
и высказывание Гриши формулой .

Полученные формулы можно рассматривать как логические уравнения и решать систему:

- ложно потому, что сосуд не может быть изготовлен

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

Это уравнение умножается на третье логическое уравнение составленной системы:

исключены как ложные. Из полученного высказывания следует, что «Сосуд изготовлен в Финикии и сосуд изготовлен в 5 веке». Это утверждение согласуется с данными поставленной задачи.

сложное высказывание простых высказываний. В состав сложных высказываний могут входить

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

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

многозначной логике высказывания могут иметь более двух истинностных значений. В 1920 г. Ян Лукасевич разработал трёхзначную логику. В ней высказывания могут принимать три значения: «истина», «ложь» и «может быть» или «неопределено». В такой логике не действует закон исключенного третьего. В 1921 г. Э. Пост выдвинул идею многозначной логики. В k – значной логике высказывания могут принимать значения от 0 до k-1, где k=3,4, 5… и т.д.

Одной из них является алгебра логика или булева алгебра (Дж.

Буль - английский математик прошлого столетия, основоположник этой дисциплины). Ее аппарат широко используют для описания схем ЭВМ, их оптимизации и проектирования.
Вся информация в ЭВМ представляется в двоичной системе счисления. Поставим в соответствие входным сигналам отдельных устройств ЭВМ соответствующие значения хi (i=1,n), а выходным сигналам - значения функций yj (j=1,m).

Рис. Представление схемы ЭВМ

(1)
где xi – i-й вход;
n – число входов;
yi – i-й выход;
m – число выходов в устройстве,
можно описывать алгоритм работы любого устройства ЭВМ.

Каждая такая зависимость у , является “булевой функцией, у которой число возможных состояний и каждой ее независимой переменной равно двум” (стандарт ISO 2382/2-76), т.е. функцией алгебры логики, а ее аргументы определены на множестве {0,1}.

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

аргументов выражается зависимостью

N=22n.

(2)

При n=0 можно определить две основные функции (N=2), не зависящие от каких-либо переменных: у0 , тождественно равную нулю (у0=0), и у1 , тождественно равную единице ( у1=1).

Технической интерпретацией функции у1=1 может быть генератор импульсов. При отсутствии входных сигналов на выходе этого устройства всегда имеются импульсы (единицы). Функция у0=0 может быть интерпретирована отключенной схемой, сигналы от которой не поступают ни к каким устройствам.

N=4. Представим зависимость значений этих функций от значения аргумента х

в виде специальной таблицы истинности (табл.).

что они определяют значение функции в зависимости от комбинации входных

сигналов. В этой таблице, как и ранее, у0=0 и y1=1. Функция y2=х, а функция у3=x- (инверсия x).

Этим функциям соответствуют определенные технические аналоги. Схема, реализующая зависимость у2=х, называется повторителем, а схема y3=х - инвертором.

При п=2, N=l6, т.е. от двух переменных, можно построить шестнадцать различных функций.

имеющая фундаментальное значение при построении основных схем ЭВМ.
 Заметим, что

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

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

связываются знаками логического сложения. Такие формы функций получили название дизъюнктивных нормальных форм (ДНФ). Если в этих функциях конъюнкции содержат все без исключения переменные в прямом или инверсном значениях, то такая форма функций называется совершенной.
Функция у4представляет собой функцию логического сложения, дизъюнкцию. Она принимает значение единицы, если значение единицы имеет хотя бы одна переменная х1 или х2:
Тождественность приведенных аналитических зависимостей можно установить, пользуясь законами алгебры логики, приведенными ниже.
Функция y5 является инверсной функцией по отношению к y4:
Она имеет название “ отрицание дизъюнкции”. Иногда в литературе встречается ее специальное название “стрелка Пирса”, по фамилии математика, исследовавшего ее свойства.

Она очень похожа на операцию обычного умножения и принимает значение

единицы в тех случаях, когда все ее переменные равны единице:
Функция y7 является инверсной функцией по отношению к у6:
Она называется “отрицание конъюнкции” или “ штрих Шеффера”. Функция к называется логической равнозначностью, она принимает значение единицы, если все ее переменные имеют одинаковое значение (или 0 или 1):
Функция y9 является инверсной по отношению к y8:
Она принимает значение единицы, если ее переменные имеют противоположные значения. Ниже будет показано, что функции у8 и у9 являются основой для построения сумматоров, так как они соответствуют правилам формирования цифр двоичных чисел при сложении (вычитании).

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

в двоичной системе счисления. Алгебра логики устанавливает правила формирования логически полного базиса простейших функций, из которых могут строиться любые более сложные. Наиболее привычным базисом является набор трех функций {инверсия, дизъюнкция, конъюнкция}. Работа с функциями, представленными в этом базисе, очень похожа на использование операций обычной алгебры.
Алгебра логики устанавливает, что существуют и другие комбинации простейших логических функций, обладающих свойством логической полноты. Например, наборы логических функций {инверсия, дизъюнкция} и {инверсия, конъюнкция} также являются логически полными. Наиболее интересны минимальные базисы, включающие по одной операции {“отрицание дизъюнкции - ˅”} и {“отрицание конъюнкции - ˄”}. Однако работа с функциями, представленными в указанных базисах, требует от специалистов по проектированию ЭВМ определенных навыков.

простейших свойств:






В алгебру логики установлен целый ряд законов, с

помощью которых возможно преобразование логических функций (ЛФ):
коммутативный (переместительный)

x1*x2=x2*x1



ассоциативный (сочетательный)

(x1*x2)*x3=(x1*x3)*x2=x1*(x2*x3)

(распределительный)




Закон поглощения. В дизъюнктивной форме ЛФ конъюнкция меньшего ранга,

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



Закон склеивания

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

Убедиться в

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