Реферат: Функционально полные системы логических функций. Алгебраический подход
--PAGE_BREAK--Чтобы не повторить или не пропустить ни одного возможного сочетания значений входных переменных, следует пользоваться одним из предлагаемых ниже способов заполнения таблицы.
Способ 1. Каждый набор значений исходных переменных есть код числа в двоичной системе счисления, причем количество разрядов числа равно количеству входных переменных. Первый набор — число 0. Прибавляя к текущему числу каждый раз по 1, получаем очередной набор. Последний набор — максимальное значение двоичного числа для данной длины кода.
Например, для функции от трех переменных последовательность наборов состоит из чисел:
000
001
010
011
100
101
110
111
9
Способ 2. Для функции от трех переменных последовательность данных можно получить следующим путем:
а) разделить колонку значений первой переменной пополам и заполнить верхнюю половину нулями, нижнюю половину единицами;
б) в следующей колонке для второй переменной половинку снова разделить пополам и заполнить группами нулей и единиц; аналогично заполнить вторую половинку;
в) так делать до тех пор, пока группы нулей и единиц не будут состоять из одного символа.
Способ 3. Воспользоваться известной таблицей истинности для двух аргументов. Добавляя третий аргумент, сначала записать первые 4 строки таблицы, сочетая их со значением третьего аргумента, равным 0, а затем еще раз записать эти же 4 строки, но теперь уже со значением третьего аргумента, равным 1. В результате в таблице для трех аргументов окажется 8 строк:
000
010
100
110
001
011
101
111
Например, построим таблицу истинности для логической функции:
<img width=«129» height=«42» src=«ref-2_1048481811-1645.coolpic» v:shapes=«Рисунок_x0020_70»>
Количество входных переменных в заданном выражении равно трем (A,B,C). Значит, количество входных наборов Q=23=8.
10
Столбцы таблицы истинности соответствуют значениям исходных выражений A,B,C, промежуточных результатов <img width=«13» height=«19» src=«ref-2_1048483456-437.coolpic» v:shapes=«Рисунок_x0020_73»> и (B V C), а также
искомого окончательного значения сложного арифметического выражения: <img width=«79» height=«36» src=«ref-2_1048483893-1053.coolpic» v:shapes=«Рисунок_x0020_76»>
A
B
C
<img width=«23» height=«32» src=«ref-2_1048484946-526.coolpic» v:shapes=«Рисунок_x0020_79»>
BVC
<img width=«86» height=«49» src=«ref-2_1048485472-1209.coolpic» v:shapes=«Рисунок_x0020_82»>
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
4. Логические функции и их преобразования. Законы логики
Для операций конъюнкции, дизъюнкции и инверсии определены законы булевой алгебры, позволяющие производить тождественные (равносильные) преобразования логических выражений.
Законы логики
1. ¬¬ А <=> A закон двойного отрицания;
2. A&B <=> B&A коммутативность конъюнкции;
3. AVB <=> BVA коммутативность дизъюнкции;
4. A&(B&C) <=> (A&B)&C ассоциативность конъюнкции;
5. AV(BVC) <=> (AVB)VC ассоциативность дизъюнкции;
6. A&(BVC) <=> (A&B)V(A&C) дистрибутивность конъюнкции относительно дизъюнкции;
7. AV(B&C) <=> (AVB)&(AVC) дистрибутивность дизъюнкции относительно конъюнкции;
11
8. A&A <=> A
9. AVA <=> A
10. AV¬A <=> И закон исключенного третьего;
11. A&¬A <=> Л закон непротиворечия;
12. A&И<=> A
13. AVИ<=> И
14. A&Л<=> Л
15. AVЛ<=> A
16. ¬(A&B) <=> ¬ A V ¬ B законы де Моргана;
17. ¬(AVB) <=> ¬ A & ¬ B
18. A => B <=> ¬ A V B замена импликации.
Основываясь на законах, можно выполнять упрощение сложных логических выражений. Такой процесс замены сложной логической функции более простой, но равносильной ей, называется минимизацией функции.
Пример 1. Упростить выражения <img width=«202» height=«28» src=«ref-2_1048486681-2148.coolpic» v:shapes=«Рисунок_x0020_85»> так, чтобы в полученных формулах не содержалось отрицания сложных высказываний.
Решение
<img width=«273» height=«93» src=«ref-2_1048488829-5826.coolpic» v:shapes=«Рисунок_x0020_88»>
Пример 2. Минимизировать функцию <img width=«312» height=«35» src=«ref-2_1048494655-3081.coolpic» v:shapes=«Рисунок_x0020_91»>
12
Решение
<img width=«334» height=«71» src=«ref-2_1048497736-5032.coolpic» v:shapes=«Рисунок_x0020_94»>
При упрощении выражения использовались формулы поглощения и склеивания.
Пример 3. Найти отрицание следующего высказывания: «Если урок будет интересным, то никто из учеников (Миша, Вика, Света) не будет смотреть в окно».
Решение
Обозначим высказывания:
Y — «Урок интересный»;
M — «Миша смотрит в окно»;
B — «Вика смотрит в окно»;
C — «Света смотрит в окно».
<img width=«302» height=«76» src=«ref-2_1048502768-5637.coolpic» v:shapes=«Рисунок_x0020_97»>
При упрощении выражения использовались формула замены операций и закон де Моргана.
Пример 4. Определить участника преступления, исходя из двух посылок:
1) «Если Иванов не участвовал или Петров участвовал, то Сидоров участвовал»;
2) «Если Иванов не участвовал, то Сидоров не участвовал».
13
Решение
Составим выражения:
I — «Иванов участвовал в преступлении»;
P — «Петров участвовал в преступлении»;
S — «Сидоров участвовал в преступлении».
Запишем посылки в виде формул:
<img width=«176» height=«39» src=«ref-2_1048508405-1633.coolpic» v:shapes=«Рисунок_x0020_100»>
Тогда
<img width=«372» height=«113» src=«ref-2_1048510038-7665.coolpic» v:shapes=«Рисунок_x0020_103»>
Проверим результат, используя таблицу истинности:
<img width=«454» height=«257» src=«ref-2_1048517703-22964.coolpic» v:shapes=«Рисунок_x0020_106»>
Ответ: Иванов участвовал в преступлении.
14
Построение логической функции по ее таблице истинности
Мы научились составлять таблицу истинности для логической функции. Попробуем решить обратную задачу. Пусть дана таблица истинности для некоторой логической функции Z(X,Y):
X
Y
Z
1
1
1
1
1
1
Рассмотрим строки, где значение истинности функции Z истинно (Z=1). Функцию для этой таблицы истинности можно составить следующим образом: Z(X,Y) = (¬ X& ¬Y)V(X& ¬Y).
Каждой строке, где функция истинна (равна 1), соответствует скобка, представляющая собой конъюнкцию аргументов, причем если значение аргумента О, то мы берем его с отрицанием. Все скобки соединены между собой операцией дизъюнкции. Полученную формулу можно упростить, применив законы логики:
Z(X,Y) <=> ((¬X& ¬Y) VX)&(( ¬X&Y)V ¬Y) <=> (XV( ¬X& ¬Y)) &( ¬YV(¬X&¬Y)) <=> ((XV¬X)&(XV ¬Y))&(( Y¬V ¬X)&( ¬YV ¬Y)) <=> (1&(XV ¬Y))&(( ¬YV ¬X)& ¬Y)<=> (XV ¬Y)&(( ¬YV ¬X)& ¬Y).
Проверьте полученную формулу: составьте таблицу истинности для функции Z(X,Y).
Запишите правила конструирования логической функции по ее таблице истинности:
1. Выделить в таблице истинности те строки, в которых значение функции равно 1.
2. Выписать искомую формулу в виде дизъюнкции нескольких логических элементов. Число этих элементов равно числу выделенных строк.
15
3. Каждый логический элемент в этой дизъюнкции записать в виде конъюнкции аргументов функции.
4. Если значение какого-либо аргумента функции в соответствующей строке таблице равно 0, то этот аргумент мы берем с отрицанием.
5. Построение логических схем
Знания из области математической логики можно использовать для конструирования электронных устройств. Нам известно, что 0 и 1 в логике не просто цифры, а обозначение состояний какого-то предмета нашего мира, условно называемых «ложь» и «истина». Таким предметом, имеющим два фиксированных состояния, может быть электрический ток. Устройства, фиксирующие два устойчивых состояния, называются бистабильными (например, выключатель, реле). Если вы помните, первые вычислительные машины были релейными. Позднее были созданы новые устройства управления электричеством — электронные схемы, состоящие из набора полупроводниковых элементов. Такие электронные схемы, которые преобразовывают сигналы только двух фиксированных напряжений электрического тока (бистабильные), стали называть логическими элементами.
На элементарном уровне конъюнкцию можно представить себе в виде последовательно соединенных выключателей, а дизъюнкцию — в виде параллельно соединенных выключателей:
<img width=«298» height=«241» src=«ref-2_1048540667-5993.coolpic» v:shapes=«Рисунок_x0020_4»>
16
Логические элементы имеют один или несколько входов и один выход, через которые проходят электрические сигналы, обозначаемые условно 0, если «отсутствует» электрический сигнал, и 1, если «имеется» электрический сигнал. Простейшим логическим элементом является инвертор, выполняющий функцию отрицания. Если на вход поступает сигнал, соответствующий 1, то на выходе будет 0. И наоборот. У этого элемента один вход и один выход. На функциональных схемах он обозначается:
<img width=«202» height=«77» src=«ref-2_1048546660-2175.coolpic» v:shapes=«Рисунок_x0020_7»>
Логический элемент, выполняющий логическое сложение, называется дизъюнктор. Он имеет, как минимум, два входа. На функциональных схемах он обозначается:
<img width=«236» height=«138» src=«ref-2_1048548835-2092.coolpic» v:shapes=«Рисунок_x0020_10»>
Логический элемент, выполняющий логическое умножение, называется конъюнктор. Он имеет, как минимум, два входа. На функциональных схемах он обозначается:
<img width=«246» height=«133» src=«ref-2_1048550927-2425.coolpic» v:shapes=«Рисунок_x0020_13»>
17
Специальных логических элементов для импликации и эквивалентности нет, т.к. А => В можно заменить на ¬А V В; А <=> В можно заменить на (A & B)V(¬A & ¬B).
Другие логические элементы построены из этих трех простейших и выполняют более сложные логические преобразования информации. Сигнал, выработанный одним логическим элементом, можно подавать на вход другого элемента, это дает возможность образовывать цепочки из отдельных логических элементов. Например:
<img width=«282» height=«120» src=«ref-2_1048553352-3434.coolpic» v:shapes=«Рисунок_x0020_16»>
Эта схема соответствует сложной логической функции F(A,B)= ¬ (А V В).
Попробуйте проследить изменения электрического сигнала в этой схеме. Например, какое значение электрического сигнала (0 или 1) будет на выходе, если на входе: А=1 и В=0.
Такие цепи из логических элементов называются логическими устройствами. Логические устройства же, соединяясь, в свою очередь образуют функциональные схемы (их еще называют структурными или логическими схемами). По заданной функциональной схеме можно определить логическую формулу, по которой эта схема работает, и наоборот.
Пример 1. Логическая схема для функции <img width=«153» height=«40» src=«ref-2_1048556786-1795.coolpic» v:shapes=«Рисунок_x0020_22»> будет выглядеть следующим образом:
18
<img width=«473» height=«176» src=«ref-2_1048558581-6758.coolpic» v:shapes=«Рисунок_x0020_19»>
Правила составления электронных логических схем по заданным таблицам истинности остаются такими же, как для контактных схем.
Пример 2. Составить логическую схему для тайного голосования трех персон A, B, C, условия которого определяются следующей таблицей истинности:
A
1
1
1
1
B
1
1
1
1
C
1
1
1
1
F
1
1
1
1
Решение
По таблице построим СДНФ логической функции и упростим ее:
<img width=«488» height=«90» src=«ref-2_1048565339-9860.coolpic» v:shapes=«Рисунок_x0020_25»> продолжение
--PAGE_BREAK--
еще рефераты
Еще работы по логике