Реферат: Алгебра логики

Лекция. Алгебра логики

/>Кроме обычной алгебрысуществует специальная, основы которой были заложены английским математиком XIXвека Дж. Булем. Эта алгебра занимается такназываемым исчислением высказываний.

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

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

Рассмотримнекоторую схему и представим ее в виде так называемого «черного»ящика.

Будемсчитать, что внутреннее содержимое ящика неизвестно.

X1,X2,X3 – входные сигналы, F– выходной сигнал.

Считаемтакже, что схема А – элементарная, т.е. нет другойсхемы Б, меньшей, чем А,которая бы содержалась в А.

Построимабстрактное устройство из элементарных устройств, типа А,Б, В и т.д. Очевидно,более сложное устройство можно построить из простых путем:

1. последовательногосоединения элементов;

2. параллельногосоединения;

3. перестановкивходов элементов.

Тогда роль Y1 для второго элемента Ббудет играть:

Y1=FА(X1,X2,X3)

Y2=FБ(X1,X2)

F=F(Y1,Y2)=F(FА(X1,X2,X3),FБ(X1,X2))

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

В связи сэтим, параллельное соединение элементов в алгебрелогики не рассматривается.

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

Поэтомуперестановка аргументов влияет на характер функции.

F=F(FА(X1,X2,X3),FБ(X2,X3)) />

F(FБ(X2,X3),FА(X1,X2,X3))

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

1. последовательноесоединение элементов;

2. перестановкавходов элементов.

Этим двумфизическим приемам в алгебре логики соответствуют:

1. принципсуперпозиции (подстановка в функцию вместо ее аргументов других функций);

2. подстановка аргументов (изменение порядка записи аргументовфункций или замена одних аргументов функциидругими).

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

Элементарные функции алгебры логики

Существуетнесколько синонимов по отношению к функциям алгебрылогики:

1. функции алгебры логики (ФАЛ);

2. переключательные функции;

3. булевские функции;

4. двоичные функции.

По меренеобходимости будем пользоваться всеми этими синонимами.

Рассмотримнекоторый набор аргументов:

<X1,X2,X3,… Хi,...Xn>

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

Чему равночисло различных наборов?

Xi = {0, 1}

Поставимкаждому набору в соответствие некоторое двоичное число:

X1,X2,...........Xn

0, 0,...........,0 нулевой набор

0, 0,...........,1 первый набор

0, 0,..........1,0 второй набор

...................

1, 1,...........,1 (2n-1)-ый набор

Очевидно, чтоколичество различных X1,X2,...........Xnn-разрядных чисел в позиционной двоичной системе есть 2n.

Допустим, чтонекоторая функция F(X1,X2,....Xn)задана на этих наборах и на каждом из них она принимает либо '0'-ое, либо '1'-ое значение.

Такую функцию называют функцией алгебрылогики или переключательной функцией.

Чему равночисло различных переключательных функций 'n' аргументов?

Т.к. функция на каждом наборе может принять значение '0' или '1', а всего различныхнаборов 2n, то общее число различных функций 'n' аргументов есть: 22n.

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

Число аргументов 1 2 3 4 5 10 Число различных перекл. ф-ций 4 16 256 65536

~4*109

~10300

Различныеустройства ЭВМ содержат десятки и сотни переменных (аргументов),поэтому понятно, что число различных устройств, отличающихся друг от друга,практически бесконечно.

Итак, нужнонаучиться строить эти сложные функции (а стало быть,и устройства), а также анализировать их.

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

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

ФАЛ одного аргумента

Чтобы задатьФАЛ, нужно задать ее значения на всех наборах аргументов.

Аргумент Х значение Наименование функции 1

F0(x)

константа '0'

F1(x)

1 переменная 'х'

F2(x)

1 инверсия 'х' (отрицание х)

F3(x)

1 1 константа '1'

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

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

Необходиморассмотреть более сложные функции, т.е. ФАЛ 2х аргументов.

Дадим такиеопределения:

1. ФАЛ, принимающиеодинаковые значения на всех наборах аргументов,называются равными.

2. ФАЛ существеннозависит от аргумента Хi,если

F(X1,X2,..., Хi-1,0,Xi+1,...,Xn) />

F(X1,X2,..., Хi-1,1,Xi+1,...,Xn)

В противномслучае она зависит не существенно, а соответствующий аргументназ. фиктивным.

Например:

Х1

Х2

Х3

F(X1,X2, Х3)

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Видно, что Х3 – фиктивный аргумент.Это показывает, что в функцию можно ввести любоечисло фиктивных аргументов, от которых онасущественно не зависит. Этот прием в дальнейшем потребуется для выполнения рядапреобразований.

Все ФАЛ от2-х аргументов. Сведем их в единую таблицу 2.1.

/>Таблица 2.1.

№ функции Значение функции на наборах логических переменных Наименование функции Обозначение функции

1 1

f0(X1,X2)

Константа «ноль»

f(X1,X2)=0

f1(X1,X2)

1 Конъюнкция, произведение

f(X1,X2)= X1& X2

f(X1,X2)= X1/> X2

f(X1,X2)= X1 · X2

f(X1,X2)= X1 X2

f2(X1,X2)

Запрет по X2

X1 Δ X2

f3(X1,X2)

1 1

Переменная X1

f(X1,X2)= X1

f4(X1,X2)

Запрет по X1

X2 Δ X1

f5(X1,X2)

1 1

Переменная X2

f(X1,X2)= X2

f6(X1,X2)

1 1 Сложение по mod2 (неравнозначность)

f(X1,X2)= X1/> X2

f7(X1,X2)

1 1 1 Дизъюнкция

f(X1,X2)= X1/>X2

f(X1, X2)= X1+ X2

f8(X1,X2)

1 Стрелка Пирса

f(X1, X2)= X1/> X2

f9(X1,X2)

1 1 Равнозначность

f(X1, X2)= X1/> X2

f(X1, X2)= X1~X2

f10(X1,X2)

1 1

Инверсия X2

f(X1, X2)=^X2

f(X1, X2)=X2

f11(X1,X2)

1 1 1

Импликация от X2 к X1

f(X1, X2)= X2/> X1

f12(X1,X2)

1 1

Инверсия X1

f(X1, X2)=^X1

f(X1, X2) = X1

f13(X1,X2)

1 1 1

Импликация от X1 к X2

f(X1, X2)= X1/> X2

f14(X1,X2)

1 1 1 Штрих Шеффера

f(X1, X2)= X1|X2

f15(X1,X2)

1 1 1 1 Константа «единица»

f(X1, X2)=1

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

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

Например:

В=<один плюс один — два>

есть истинноевысказывание.

Рассмотрим,какое смысловое содержание можно вложить в некоторые сложные высказывания напримере ФАЛ 2-х аргументов.

Инверсия

Читается НЕ Х или Х с чертой, отрицание Х.

Возьмем,например, такое высказывание: А=<Киев-столицаФранции>, тогда сложное высказывание НЕ Аозначает: не верно, что А, т.е. не верно, что <Киев-столица Франции>.

Из простыхвысказываний можно строить более сложные, применяя так называемые связи.

Логическиесвязи – это ФАЛ, аргументами которых являютсяпростые высказывания.

Конъюнкция

Возьмем 2высказывания:

А=<Москва – столица РФ>

В=<дважды два — четыре>

тогда сложноевысказывание: А & В будет истинным, так какистинны оба этих высказывания.

Посколькутаблица истинности для конъюнкции совпадает стаблицей умножения, если истинному высказыванию приписать значение '1', а ложному — '0', тосложное высказывание можно назвать произведением.

f1(X1,X2)

1 1 1 1 1

Функция конъюнкции истинна тогда, когда истинны одновременно оба высказывания.

Дизъюнкция

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

f1(X1,X2)

1 1 1 1 1 1 1

Читается X1 ИЛИ X2:Некоторое отличие от смысла союза «или», принятого в русском языке: вданном случае этот союз употребляется в смысле объединения, а не разъединения.

Логическая равнозначность

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

Отсюдаследует, что вне зависимости от смысла, равнозначными являются как истинные,так и ложные высказывания.

Например,

А=<дважды два — пять>

B=<один плюс два — шесть>

А~В равнозначны.

Импликация

Это сложноевысказывание ложно только тогда, когда X1– истинно, а X2 – ложно.

f1(X1,X2)

1 1 1 1 1 1 1

Читается:если X1, то X2.При этом X1 – посылка, X2 – следствие.

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

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

Тогда изложной посылки может следовать ложное следствие и это можно считать верным: <еслиКиев – столица Франции>, то <2-квадрат 3>.

Эквивалентности

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

Дизъюнкция:

х /> х /> х /> х />… /> х /> х /> х= х,

т.е.истинность высказывания не изменится, если его заменить более коротким, такимобразом, это правило приведения подобных членов:

– постоянноистинное высказывание.

0 />x = x

x1/>x2= x2/>x1

— (переместительный) коммуникативный закон.

x1/>х2/>х3 = (x1/>х2)/>х3 = x1/>(х2/>х3)

— сочетательный закон.

Конъюнкция:

х />х />х />х… />х />х />х= х

правилоприведения подобных членов: