Студопедия
МОТОСАФАРИ и МОТОТУРЫ АФРИКА !!!


Авиадвигателестроения Административное право Административное право Беларусии Алгебра Архитектура Безопасность жизнедеятельности Введение в профессию «психолог» Введение в экономику культуры Высшая математика Геология Геоморфология Гидрология и гидрометрии Гидросистемы и гидромашины История Украины Культурология Культурология Логика Маркетинг Машиностроение Медицинская психология Менеджмент Металлы и сварка Методы и средства измерений электрических величин Мировая экономика Начертательная геометрия Основы экономической теории Охрана труда Пожарная тактика Процессы и структуры мышления Профессиональная психология Психология Психология менеджмента Современные фундаментальные и прикладные исследования в приборостроении Социальная психология Социально-философская проблематика Социология Статистика Теоретические основы информатики Теория автоматического регулирования Теория вероятности Транспортное право Туроператор Уголовное право Уголовный процесс Управление современным производством Физика Физические явления Философия Холодильные установки Экология Экономика История экономики Основы экономики Экономика предприятия Экономическая история Экономическая теория Экономический анализ Развитие экономики ЕС Чрезвычайные ситуации ВКонтакте Одноклассники Мой Мир Фейсбук LiveJournal Instagram

I.3. Функции и формулы алгебры логики




Алгебра логики задается двумя множествами: U и Р2, где U – это множество всех высказываний, принимающих значения «истина» или «ложь», или любое другое множество, элементы которого могут принимать одно их двух значений или находиться в одном из двух состояний. Например, множество переключателей, каждый из которых может быть «включен» или «выключен», или множество электрических сигналов, поступающих на вход некоторого устройства, – «сигнал есть» или «сигнала нет» и т.п.. Сопоставим значению «истина» символ «1», а значению «ложь» – символ «0». Таким образом, алгебра логики оперирует на множестве всех высказываний со значениями из двухэлементного множества Е2 ={0, 1}.

Множество Р2 – это множество всех таких функций, которые принимают «истинностные» значения 0 или 1, если их аргументы пробегают те же значения. Т.е., если f(x1,x2,…,xn) – истинностная функция от n аргументов или f(x1,x2,…,xnР2, то она определяет отображение f: ® E2. Алгебра логики занимается изучением свойств этих функций.

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

Число всех функций алгебры логики от n переменных равно 22n.

Функции алгебры логики могут быть заданы одним из следующих способов: 1) словесное описание;

2) табличное представление;

3) графическое изображение;

4) алгебраическое (в виде формулы).

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

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

x g1(x) g2(x) g3(x) g4(x)
 
Таблица 1

В таблице 1 функция g1(x) – это константа ноль или «противоречие».

Функция g2(x) – «тождественная функция x».

Функция g3(x) – «отрицание x», обозначается « » или « ».

Функция g4(x) – константа единица или «тавтология».

x y f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15 f16
Обозначение & x y Å Ú ¯ º y®x x®y |
                      Таблица 2

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




Функция f1(x,y) – это так же, как и в таблице 1, константа ноль или «противоречие».

Функция f2(x,y)=x&y – «конъюнкция» х и у или «логическое умножение». Читается: «х и у». Значения этой функции можно получить простым умножением значений её аргументов или как наименьшее из значений аргументов, т.е. f2(x,y) = x&y = x×y = min(x, y).

Функции f3(x,y)= и f5(x,y)= – это «условное вычитание» у из х, и х из у,соответственно. Их значения можно получить по правилу: и .

Функции f4(x,y)=х и f6(x,y)=у – как и в таблице 1, «тождественная функция x» и «тождественная функция у» соответственно.

Функция f7(x,y)=хÅу – «сложение по модулю 2» или «исключающее или». Значения этой функции равны остатку от деления на 2 суммы её аргументов.

Функция f8(x,y)=хÚу – «дизъюнкция» х и у или «логическое сложение». Читается: «х или у». Значения этой функции можно получить как наибольшее из значений аргументов, т.е. f2(x,y) = xÚy = max(x, y).

Функция f9(x,y)=х¯у – «стрелка Пирса» или «отрицание дизъюнкции» или «конъюнкция отрицаний». Последние два названия обусловлены правилом, по которому получаются значения этой функции.

Функция f10(x,y)=хºу – «эквиваленция». Читается: «х эквивалентно у». Значения этой функции получаются по правилу: .



Функции f11(x,y)= и f13(x,y)= – это так же, как и в таблице 2, «отрицание у» и «отрицание х» соответственно.

Функции f12(x,y)= y®x и f14(x,y)= x®y – это так называемая «импликация». Для чтения выражения x®y можно использовать фразу «х влечет у» или «если х, то у». Значения x®y получаются как ответ на вопрос «х меньше, либо равно у?». При этом положительный ответ записывается «1», а отрицательный – «0».

Функция f15(x,y)= y | x – «штрих Шеффера» или «отрицание конъюнкции» или «дизъюнкция отрицаний». Последние два названия обусловлены правилом, по которому получаются значения этой функции.

Последняя функция в таблице 2 – это так же, как и в таблице 1, константа единица или тавтология.

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

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

Для построения полной таблицы истинности исходную формулу разделяют на подформулы и затем вычисляют значение каждой подформулы. Таким образом, если n – это число переменных в формуле, а s – число выделенных подформул, то число столбцов в полной таблице истинности исходной формулы будет равно n+s, а число строк – 2n. При этом последний столбец этой таблицы будет представлять значения формулы.

Для примера рассмотрим построение полной таблицы истинности формулы . Разделим её на подформулы: f1x, f2=f1Úy, f3=f2®z. Тем самым, таблица будет содержать 8 строк и 6 столбцов. См. таблицу 3.

x y z f1 f2 f3
Таблица 3

В последнем столбце таблицы 3 находятся значения исходной формулы.

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

((Ø x Ú y) ® z)  
 
 
 
 
 
 
 
0 Таблица 4

Рассмотрим построение сокращенной таблицы истинности на примере той же формулы: . См. таблицу 4.

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

Из рассмотренных примеров видно, что значениями формулы могут быть только 0 или 1. Поэтому столбец результатов можно рассматривать, как некоторую истинностную функцию, принимающую те же значения, что и формула, на соответствующих «энках». Об этой функции говорят, что она реализуется формулой, про формулу, – что она реализует функцию.

Две формулы А и В называются эквивалентными, если функции fA и fB, соответствующие им, эквивалентны или равны, т.е. fA=fB. Для обозначения эквивалентных формул традиционно используется запись А=В, которую называют тождеством.

Следующие тождества характеризуют важнейшие свойства элементарных функций: {0, 1, Ø, &, Ú}. (Обозначим «∘» любую из функций: {&, Ú, Å}.)

1) ((xy)∘z)=(x∘(yz)) – свойство ассоциативности;

2) (xy)=(yх) – коммутативность;

3) конъюнкция и дизъюнкция дистрибутивны друг относительно друга: ((x Ú y) & z) = ((x & z) Ú (y & z))
((x & y) Ú z) = ((x Ú z) & (y Ú z));

4) – закон двойного отрицания;

5) – законы Де Моргана для конъюнкции и дизъюнкции;

6) (х & х) = x; (x Ú x) = x – законы идемпотентности;

7) – закон исключенного третьего;

8) – закон противоречия;

9) (х & 0) = 0, (x Ú 0) = x – умножение на ноль и сложение с нулем;

10) (х & 1) = х, (x Ú 1) = 1 – умножение на единицу и сложение с единицей;

11) ((х & y) Ú x) = x, ((х Ú y) & x) = x – законы поглощения.

Все тождества легко проверяются с помощью таблиц истинности.

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

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

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

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

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

д) пусть U1 – подформула формулы U; если в формуле U заменить любые вхождения подформулы U1 эквивалентной ей формулой В1, то в результате будет получена формула В, эквивалентная исходной формуле U.

Для упрощения записи формул вводятся следующие соглашения:

1) В формулах опускают внешнюю пару скобок, т.е. вместо формулы (х®у) пишут выражение х®у. Аналогично в выражениях со знаком отрицания вместо записывают .

2) По закону ассоциативности для операции «∘» вместо формулы ((x y) ∘ z) или (x∘(y z)) используется выражение без скобок: xy z. Для восстановления формулы достаточно расставить скобки, порядок которых не является существенным для вычислений.

3) О старшинстве операций: если в выражении с помощью скобок специально не указан порядок выполнения операций, то одинаковые по старшинству операции выполняются последовательно слева направо. Если в выражении имеются различные операции, то сначала выполняется отрицание, затем конъюнкция, дизъюнкция, импликация и т.д., самой последней выполняется эквиваленция. Скобки восстанавливаются по тому же правилу.

Ввиду введенного старшинства операций не всякая формула может быть записана без скобок. Например, в выражениях х®(у®z) или х&(yÚz) дальнейшее исключение скобок невозможно, т.к. это может повлиять на значение, вычисленное по формуле.

4) Для компактности вместо записи х1&x2&…&xs используется запись , а вместо х1Úx2Ú…Úxs .

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

Рассмотрим эквивалентные преобразования формулы: 1= 2= 3= 4= 5=

Тождество 1 записано по правилу сокращения единичного сомножителя, тождество 2 – по правилу замены подформулы эквивалентной формулой, а именно: здесь для замены использовался закон исключенного третьего. В тождестве 3 применен закон дистрибутивности. Тождество 4 получено по закону коммутативности. И, наконец, тождество 5 записано по закону поглощения, причем для наглядности «поглощающие элементы» подчеркнуты одинарной и двойной чертой.





Дата добавления: 2015-10-22; просмотров: 1594; Опубликованный материал нарушает авторские права? | Защита персональных данных | ЗАКАЗАТЬ РАБОТУ


Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: На стипендию можно купить что-нибудь, но не больше... 9317 - | 7382 - или читать все...

Читайте также:

 

3.229.118.253 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.


Генерация страницы за: 0.009 сек.