МАТЕМАТИЧЕСКАЯ ЛОГИКА. ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ И ПРЕДИКАТОВ
Функции алгебры логики и их основные свойства
Математическая логика – это анализ методов рассуждений. При этом исследуются формы рассуждений, а не их содержание. Формализация рассуждений, ведущая начало от Аристотеля, приобрела современный вид во второй половине 19-го в. в сочинении Джорджа Буля "Законы мысли". Наибольший расцвет математической логики начался в 50-е гг. 20-го в. в связи с бурным развитием цифровой техники. Учение о высказываниях, называемое алгеброй высказываний, является первой из формальных логических теорий, и знакомство с законами алгебры высказываний облегчает изучение исчисления высказываний и исчисления предикатов. Кроме того, алгебра высказываний представляет самостоятельный интерес и имеет большое приложение при синтезе электронных схем [15, 16] .
Анализ рассуждений основывался на анализе так называемых логических функций, которые определяются путем задания области определения и области значения функций. Для этого рассмотрим набор < х1, х2,,.,,хn>, в котором переменные x могут принимать значения 0 или 1 ("ложь "или "истина"). При этом количество различных числовых наборов такого вида равно 2n . Функция, определенная на таких наборах и принимающая в качестве своих значений на этих наборах 0 или 1, называется функцией алгебра логики (ФАЛ), или булевой функцией. Так как число различных наборов является конечным, то любая ФАЛ может быть полностью задана конечной таблицей с 2n строками. Переменные х1, х2,,.,,хn называются аргументами функции алгебры логики. Если две функции и принимают на всех 2n наборах одинаковые значения, то функции и считаются равными. При этом функции алгебры логики могут не зависеть от некоторых элементов набора Функция существенно зависит от аргумента , если имеет место соотношение
|
|
В противном случае говорят, что функция несущественно зависит от аргумента . Функция, в которой какому-то аргументу придано значение 0 или 1, называется соответственно нулевой или единичной остаточной функцией. Они в этом случае являются функциями от n – 1 аргументов. Нетрудно показать, что существует различных функций от n аргументов (табл.4.1). В этой таблице справа записана одна из функций алгебры логики, зависящая от n аргументов. Задавая тот или иной конкретный двоичный набор , мы будем задавать одну из возможных функций алгебры логики. Число наборов равно числу 2n разрядных двоичных чисел, т.е. .В число функций алгебры логики входят как функции, существенно зависящие от всех n аргументов, так и функции, для которых часть из этих аргументов являются фиктивными. Например, для n =1 имеем =4 различные функции (табл.4.2).
|
|
В этом случае только функции и существенно зависят от x1, а для функций и этот единственный аргумент является фиктивным. Число всех функций алгебры логики, существенно зависящих от n аргументов, определяется следующим рекуррентным соотношением [16]:
(4.2)
В этом соотношении Аi есть число ФАЛ, существенно зависящих от i аргументов. Из последнего примера следует, что А0 = 2, А1 = 2. Тогда . Рассмотрение множества элементарных функций алгебры логики начнем со случая n = 0. Имеются только две функции, совпадающие с константами 0 и 1:
Таблица 4.1
0 0 … 0 0 | ………………… | . | |
0 0 … 0 1 | ………………… | . | |
0 0 … 1 0 | 1 1 … 1 1 |
Таблица 4.2
0 | 0 | 1 | 0 | 1 |
1 | 0 | 1 | 1 | 0 |
Таблица 4.3
0 | 0 | 1 |
1 | 1 | 0 |
В случае n = 1 имеем две функции, существенно зависящие от одного аргумента. Они определяются табл. 4.3.
Эти две функции обозначим Функция 4 называется отрицанием. Читается "не х". Построим все булевы функции от двух переменных (табл. 4.4).
Из этих шестнадцати функций, как было показано, существенно зависящих от двух аргументов, будет лишь десять функций, из которых семь являются существенно различными и имеют важное значение при построении логических схем. Нетрудно видеть, что введенные функции – это функция – константа нуль; – это функция – константа единица; – это функция согласно табл. 4.3 – переменная х1 (аналогично ); – это функция (отрицание х1), аналогично – отрицание х2.
|
|
Семь существенно зависящих от двух аргументов функций имеют следующие названия:
– функция дизъюнкции или логического сложения (в табл. 4. 4 это функция );
– функция конъюнкции (в табл. 4.4 это функция );
– функция равнозначности (эквивалентности) (в табл.4.4 это функция );
– функция импликации х1 в х2. Читается «если х1, то х2» (в табл. 4.4 это аналогично
– функция Вебба (отрицание дизъюнкции: в табл. 4.4 это функция );
– функция Шеферра (отрицательные конъюнкции; в табл. 4.4 это функция );
– функция сложения по модулю два.
Таблица 4.4
х1 | х2 | ||||||||||||||||
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
|
|
Таблицы типа табл. 4.3 и 4.4, задающее значения функций на всех возможных наборах, называется таблицами истинности. Рассмотренные одиннадцать функций позволяют строить новые функции алгебры логики путем:
– перенумерации аргументов;
– подстановки в функцию новых функций вместо аргументов.
Используя таблицы истинности, определяющие элементарные функции, можно задавать в виде таблицы истинности любую ФАЛ, являющуюся суперпозицицией этих функций. Пусть требуется представить в виде таблицы функцию:
Будем строить функцию последовательно (табл.4.5).
Таблица 4.5
х1 | х2 | х3 | [ ] | { } | |||||
0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 |
0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 |
0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 |
0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 |
1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 0 |
1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 |
1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 |
1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
Таблицы истинности можно использовать для проверки равенстве или неравентсва различных ФАЛ. Рассмотрим отдельным важные примеры (табл. 4.6 – 4.11).
Таблицы 4.6 Таблицы 4.7
х1 | х2 | |
0 | 0 | 1 |
0 | 1 | 1 |
1 | 0 | 0 |
1 | 1 | 1 |
х1 | х2 | ||
0 | 0 | 1 | 1 |
0 | 1 | 1 | 1 |
1 | 0 | 0 | 0 |
1 | 1 | 0 | 1 |
Таблицы 4.8 Таблицы 4.9
Х1 | х2 | |
0 | 0 | 0 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
х1 | х2 | ||||
0 | 0 | 1 | 1 | 1 | 0 |
0 | 1 | 1 | 0 | 1 | 0 |
1 | 0 | 0 | 1 | 1 | 0 |
1 | 1 | 0 | 0 | 0 | 1 |
Таблицы 4.10 Таблицы 4.11
х1 | х2 | |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 1 |
х1 | х2 | ||||
0 | 0 | 1 | 1 | 1 | 0 |
0 | 1 | 1 | 0 | 0 | 1 |
1 | 0 | 0 | 1 | 0 | 1 |
1 | 1 | 0 | 0 | 0 | 1 |
Последние две формулы носят название формул де Моргана и могут быть обобщены:
Особую роль в развитии методов синтеза электронных схем сыграли функции – соответственно отрицания, дизъюнкции и конъюнкции. Поэтому отдельно остановимся на их свойствах. Функция Функции дизъюнкции и конъюнкции обладают рядом свойств, аналогичны свойствам обычных операций умножения и сложения. Для этих функций справедливы сочетательный:
переместительный
и распределительный законы конъюнкции относительно дизъюнкции:
(4.5)
Кроме того, имеет место распределительный закон дизъюнкции относительно конъюнкции:
(4.6)
который не имеет места в обычной алгебре, так как если бы он существовал, то имел бы вид
Справедливость распределительного закона дизъюнкции относительно конъюнкции легко устанавливается путем построения таблиц истинность для правой и левой частей формулы, отражающей этот закон.
Все введенные функции, кроме аналитической записи, имеют и содержательный смысл. Верно и обратное: любое сложное высказывание можно записать в виде функции от простых высказываний. Например, рассмотрим высказывание: "Если две стороны одного треугольника и угол между ними равны соответственно двум сторонам другого треуголъника и углу между ними, то такие треугольники равны". Это высказывание легко расчленить на следующие три высказывания: "Две стороны одного треугольника равны соответственно двум сторонам другого треугольника", "Угол, заключенный между этими сторонами одного треугольника, равен соответствующему углу другого треугольника". "Такие треугольники равны". Если обозначить: х1 – первое высказывание; х2 – второе высказывание; – третье высказывание), то получим связь истинности и ложности этих высказываний в виде таблицы истинности:
Таблица 4.12
х1 | х2 | |
0 | 0 | 0 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
Нетрудно видеть, что это есть таблица истинности для функции – функции конъюнкции: если х1 и х2, то
Очевидно, что и другие более сложные высказывания могут быть записаны в виде формул алгебры логики через введенные ранее функции При этом встают вопросы о различных аналитических выражениях высказываний и их минимальном (наиболее экономном с точки зрения количества входящих символов и их числа) представлении. С этой целью разобьем все множество функций алгебры логики на классы и сформулируем одну из основных теорем, отвечающую на вопрос о количестве необходимых функций для полного описания высказываний.
Дата добавления: 2018-11-24; просмотров: 269; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!