Содержание
Кроме знаков операций, в алгебре Буля применяются знак “=” (равно) и скобки. Знак “равно” указывает, конечно, не количественное равенство, а то, что разделяемые им символы идентичны, поэтому сигналы слева от этого знака всюду можно заменить символами справа от него и наоборот. Например, если y1 = 
, y2 = 
, y3 = 
, а z = y1 + y2 + y3 , то можно записать
z = y1 + y2 + y3 = 
+ + .
Суперпозиция булевых функций может быть записана как математическая формула, которую называют логической формулой.
Скобки, как и в обычной алгебре, применяются для дополнительного указания порядка выполнения (приоритета) операций. Для уменьшения числа скобок используется приоритет операций.
Приоритет (порядок выполнения) логических операций следующий:
1. Вычисляются значения выражений внутри скобок;
2. Выполняются отрицания над отдельными переменными (НЕ);
3. Вычисляются конъюнкции (И, И-НЕ);
4. Вычисляются дизъюнкции (ИЛИ, ИЛИ-НЕ);
5. Вычисляются суммы по модулю 2 и функции равнозначности;
6. Вычисляется импликация.
Заметим, что иногда знак отрицания ставится над целым выражением, не заключённым в скобки; в этом случае отрицание выполняется в последнюю очередь.
Пример 2.2. Логическая формула
,
с учётом правил приоритета может быть записана так:
.
Не нашли то, что искали? Воспользуйтесь поиском:
Лучшие изречения: Увлечёшься девушкой-вырастут хвосты, займёшься учебой-вырастут рога 9970 — 
| 7768 — 
или читать все.
91.146.8.87 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.
Отключите adBlock!
и обновите страницу (F5)
очень нужно
При вычислении логического выражения логические операции вычисляются в определенном порядке:
1) Инверсия; 2) конъюнкция; 3) дизъюнкция, 4) исключающее или; 5) импликация; 6)эквивалентность.
Операции одного приоритета выполняются слева направо. Порядок действий изменяется скобками
Практическое задание
Используя таблицы истинности логических операций, определите значение логического выражения:
2. Логические выражения и таблицы истинности
Таблицу, показывающую, какие значения принимает составное высказывание при всех сочетаниях (наборах) значений входящих в него простых высказываний, называют таблицей истинности составного высказывания. Составные высказывания записываются с помощью логических выражений, для любого логического выражения можно построить таблицу истинности.
Чтобы построить таблицу истинности нужно:
определить количество строк, оно равно количеству возможных комбинаций значений логических переменных, входящих в логическое выражение. Если количество логических переменных n, то количество строк = 2 n ;
определить количество столбцов, которое равно количеству логических переменных плюс количество логических операций;
построить таблицу истинности с указанным количеством строк и столбцов, обозначить столбцы и внести возможные наборы значений исходных логических переменных;
заполнить таблицу истинности по столбцам, выполняя базовые логические операции в необходимой последовательности в соответствии с их таблицами истинности.
Пример 1. Построить таблицу истинности для выражения F = (A B) & ( A B ) алгебраически и с помощью электронных таблиц.
Решение. Количество логических переменных 2, поэтому количество строк в таблице истинности равно 2 2 = 4. Количество логических операции в формуле 5, поэтому количество столбцов должно быть: количество переменных + количество операций, т. е. 2 + 5 = 7.
А) Построение таблице истинности алгебраически (табл. 1).
Операции в логическом выражении выполняются слева направо с учетом скобок в следующем порядке:
Для изменения указанного порядка выполнения логических операций используются круглые скобки.
Составные логические выражения алгебры высказываний называют формулами.
Истинно или ложно значение формулы можно определить законами алгебры логики, не обращаясь к смыслу:
F = (0/1)/(1/1) = (1/ ) /(0/0) = 0/0 = 0 – ложь.
А при сложном логическом выражении здесь, порядок выполнения логических операций:
1. действия в скобках.
6. Эквивалентность «.
7. для изменения указанного порядка выполнения операций используются скобки.
3.8. Логические выражения и таблица истинности
Таблица истинности — таблица, показывающая, какие значения принимает составное высказывание при всех сочетаниях (наборах) значений входящих в него простых высказываний.
Логическое выражение — составные высказывания в виде формулы.
Равносильные логические выражения – логические выражения, у которых последние столбцы таблиц истинности совпадают. Для обозначения равносильности используется знак «=».
Алгоритм построения таблицы истинности:
1. подсчитать количество переменных n в логическом выражении;
2. определить число строк в таблице по формуле m=2 n , где n — количество переменных;
3. подсчитать количество логических операций в формуле;
4. установить последовательность выполнения логических операций с учетом скобок и приоритетов;
5. определить количество столбцов: число переменных + число операций;
6. выписать наборы входных переменных;
7. провести заполнение таблицы истинности по столбцам, выполняя логические операции в соответствии с установленной в пункте 4 последовательностью.
Заполнение таблицы:
1. разделить колонку значений первой переменной пополам и заполнить верхнюю часть «0», а нижнюю «1»;
2. разделить колонку значений второй переменной на четыре части и заполнить каждую четверть чередующимися группами «0» и «1», начиная с группы «0»;
3. продолжать деление колонок значений последующих переменных на 8, 16 и т.д. частей и заполнение их группами «0» или «1» до тех пор, пока группы «0» и «1» не будут состоять из одного символа.
Пример 1. Для формулы A/(B/ B/ C) постройте таблицу истинности.
Количество логических переменных 3, следовательно, количество строк — 2 3 = 8. Количество логических операций в формуле 5, количество логических переменных 3, следовательно, количество столбцов — 3 + 5 = 8.
| А | В | С | -В | -С | -ВÙ-С | ВÚ-ВÙ-С | АÙ(ВÚ-ВÙ-С) |
| 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 | 1 | |||
| 1 | 1 | 1 | 1 | 1 |
Пример 2 . Определите истинность логического выражения F(А, В) = (А/ В)/(А/В) .
1. В выражении две переменные А и В (n=2).
2. mстрок=2 n , m=2 2 =4 строки.
3. В формуле 5 логических операций.
4. Расставляем порядок действий.
1) А/ В; 2) А; 3) В; 4) А/В; 5) (А/ В)/(А/В).
5. Кстолбцов=n+5=2+5=7 столбцов.
| А | В | А/ В | А | В | А/В | F |
| 1 | 1 | 1 | ||||
| 1 | 1 | 1 | 1 | 1 | ||
| 1 | 1 | 1 | 1 | 1 | ||
| 1 | 1 | 1 |
Вывод: логическое выражение принимает значение истина при наборах F(0,1)=1 и F(1,0)=1.
Пример 3. Построите таблицу истинности для логического выражения
F =(A/ B)/С.
1. В данной функции три логические переменные – А, В, С.
2. Количество строк таблицы = 2 3 =8.
3. В формуле 3 логические операции.
4. Расставляем порядок действий: 1) А/ В; 2) С; 3) (AVB)/С .
5. Количество столбцов таблицы = 3 + 3 = 6.
| А | В | С | A/B | С | (A/B) / С |
| 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. Определите истинность формулы: F =((С/В )=>В)/(А /В) =>В. Построим таблицу истинности этой формулы.
| А | В | С | СÚВ | (СÚВ)®В | АÙВ | ((СÚВ)®ВÙ(АÙВ) | F |
| 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 | 1 | 1 | 1 | |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Ответ: формула является тождественно истинной.
Пример 5. Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z.
Дан фрагмент таблицы истинности выражения F:
| X | Y | Z | F |
| 1 | |||
| 1 | |||
| 1 | 1 |
Какое выражение соответствует F?
Решение (вариант 1, через таблицы истинности):
Чтобы решить данную задачу можно построить часть таблицы истинности для каждой из четырех функций, заданных в ответе для заданных наборов входных переменных, и сравнить полученные таблицы с исходной:
| X | Y | Z | F | X | Y | Z | X/Y/ | X/Y/Z | X/Y/Z | X/Y/Z |
| 1 | 1 | 1 | 1 | 1 | 1 | |||||
| 1 | 1 | 1 | 1 | 1 | 1 | |||||
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Очевидно, что значения заданной функции F совпадают со значениями выражения X/Y/Z. Следовательно, правильный ответ – 3.
Решение (Вариант 2):
Чтобы не строить таблицу истинности для каждого выражения, можно просто перепроверить предложенные ответы по заданной таблице истинности. Т.е. в каждую из четырех предложенных функций последовательно подставлять значения переменных X, Y и Z, из заданной таблицы истинности и вычислять значения логического выражения. Если значения вычисляемого выражения совпадут со значением F во всех трех строчках заданной таблицы, то это и есть искомое выражение.
Рассмотрим данный конкретный пример:
1) первое заданное выражение X/Y/= 0 при X=0, Y=0, Z=0, что не соответствует первой строке таблицы;
2) второе заданное выражение X/Y/Z= 1 при X=0, Y=0, Z=1, что не соответствует второй строке таблицы;
3) третье выражение X/Y/Z соответствует F при всех предложенных комбинациях X, Y и Z;
4) четвертое выражение X/Y/Z = 1 при X=0, Y=0, Z=1, что не соответствует второй строке таблицы. Ответ 3.
Пример 1:Составить таблицу истинности для логических функции
.
1. Определить порядок действий: 
.
2. Определить размерность таблицы истинности.
«Шапка» таблицы содержит две строки-номера действий и логические операции действий. Количество столбцов определяется количеством логических переменных (их две А, В) и количеством действий (их тоже два).
Количество строк в таблице равно двойке в степени, равной количеству логических переменных – в случае двух переменных получается 4 строки.
| 1 | 2 | ||
| А | В |  |
1  В |
3. Поочередно заполнить столбики таблицы в соответствии с логической функцией данного столбца.
| 1 | ||
| А | В | |
| 1 | ||
| 1 | 1 | |
| 1 | ||
| 1 | 1 |
| 1 | 2 | ||
| А | В | |
1 В |
| 1 | 1 | ||
| 1 | 1 | 1 | |
| 1 | |||
| 1 | 1 | 1 |
4. Сформулировать ответ. В последнем столбце один «0», соответствующий А, равному «1», и В, равному «0». Получается, что данная функция ложна тогда и только тогда, когда логическая переменная А истинна, а логическая переменная В ложна, что соответствует логической функции СЛЕДСТВИЕ.
Значит данная функция равна логическому следствию переменных А и В: Если А то В. 
.
Пример 2: 
. Определить порядок действий. 
.
Определить размерность таблицы истинности.
«Шапка» таблицы содержит две строки-номера действий и логические операции действий. Количество столбцов определяется количеством логических переменных (их две А, В) и количеством действий (их тоже два).
Количество строк в таблице равно двойке в степени, равной количеству логических переменных – в случае двух переменных получается 4 строки.
1. Поочередно заполнить столбики таблицы в соответствии с логической функцией данного столбца.
4. Сформулировать ответ. В последнем столбце один «1», соответствуют А, равному В, а «0» — А неравному В. Получается, что данная функция истина, когда А равно В и ложна, когда А не равно В, что соответствует логической функции ТОЖДЕСТВО.
Значит данная функция равна логическому тождеству А и В: А тождественно В. 
.
Дата добавления: 2019-09-08 ; просмотров: 114 ; ЗАКАЗАТЬ РАБОТУ
Загрузка...
