Приоритет логических операций в сложном логическом выражении
Операции в логическом выражении выполняются слева направо с учетом скобок в следующем порядке:
1. инверсия;
2. конъюнкция;
3. дизъюнкция.
Для изменения указанного порядка выполнения логических операций используются круглые скобки.
Составные логические выражения алгебры высказываний называют формулами.
Истинно или ложно значение формулы можно определить законами алгебры логики, не обращаясь к смыслу:
F = (0\/1)/\(0\/1)=(0\/1)/\(1\/0)=1/\1=1–истина,
F = (0/\1)\/(1\/1) = (1/\0) \/(0\/0) = 0\/0 = 0 – ложь.
А при сложном логическом выражении здесь, порядок выполнения логических операций:
1. действия в скобках.
2. инверсия.
3. конъюнкция Λ.
4. дизъюнкция V.
5. импликация →.
6. Эквивалентность «.
7. для изменения указанного порядка выполнения операций используются скобки.
3.8. Логические выражения и таблица истинности
Таблица истинности - таблица, показывающая, какие значения принимает составное высказывание при всех сочетаниях (наборах) значений входящих в него простых высказываний.
Логическое выражение - составные высказывания в виде формулы.
Равносильные логические выражения – логические выражения, у которых последние столбцы таблиц истинности совпадают. Для обозначения равносильности используется знак «=».
Алгоритм построения таблицы истинности:
1. подсчитать количество переменных n в логическом выражении;
2. определить число строк в таблице по формуле m=2n, где 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, следовательно, количество строк - 23 = 8. Количество логических операций в формуле 5, количество логических переменных 3, следовательно, количество столбцов - 3 + 5 = 8.
| А | В | С | -В | -С | -ВÙ-С | ВÚ-ВÙ-С | АÙ(ВÚ-ВÙ-С) |
| 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 |
Пример 2 . Определите истинность логического выражения F(А, В) = (А\/ В)/\(А\/В) .
|
|
|
1. В выражении две переменные А и В (n=2).
2. mстрок=2n, m=22=4 строки.
3. В формуле 5 логических операций.
4. Расставляем порядок действий.
1) А\/ В; 2) А; 3) В; 4) А\/В; 5) (А\/ В)/\(А\/В).
5. Кстолбцов=n+5=2+5=7 столбцов.
| А | В | А\/ В | А | В | А\/В | F |
| 0 | 0 | 0 | 1 | 1 | 1 | 0 |
| 0 | 1 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 |
Вывод: логическое выражение принимает значение истина при наборах F(0,1)=1 и F(1,0)=1.
Пример 3. Построите таблицу истинности для логического выражения
F =(A\/ B)/\С.
1. В данной функции три логические переменные – А, В, С.
2. Количество строк таблицы = 23 =8.
3. В формуле 3 логические операции.
4. Расставляем порядок действий: 1) А\/ В; 2) С; 3) (AVB)/\С .
5. Количество столбцов таблицы = 3 + 3 = 6.
| А | В | С | A\/B | С | (A\/B) /\ С |
| 0 | 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 |
Пример 4. Определите истинность формулы: F =((С\/В )=>В)/\(А /\В) =>В. Построим таблицу истинности этой формулы.
|
|
|
| А | В | С | СÚВ | (СÚВ)®В | АÙВ | ((СÚВ)®ВÙ(АÙВ) | F |
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Ответ: формула является тождественно истинной.
Пример 5. Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z.
Дан фрагмент таблицы истинности выражения F:
| X | Y | Z | F |
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 |
Какое выражение соответствует F?
1) X/\Y/\Z 2) X\/Y\/Z
3) X\/Y\/Z 4) X\/Y\/Z.
Решение (вариант 1, через таблицы истинности):
Чтобы решить данную задачу можно построить часть таблицы истинности для каждой из четырех функций, заданных в ответе для заданных наборов входных переменных, и сравнить полученные таблицы с исходной:
| X | Y | Z | F | X | Y | Z | X/\Y/\Z | X\/Y\/Z | X\/Y\/Z | X\/Y\/Z |
| 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 |
| 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 |
Очевидно, что значения заданной функции F совпадают со значениями выражения X\/Y\/Z. Следовательно, правильный ответ – 3.
|
|
|
Решение (Вариант 2):
Чтобы не строить таблицу истинности для каждого выражения, можно просто перепроверить предложенные ответы по заданной таблице истинности. Т.е. в каждую из четырех предложенных функций последовательно подставлять значения переменных X, Y и Z, из заданной таблицы истинности и вычислять значения логического выражения. Если значения вычисляемого выражения совпадут со значением F во всех трех строчках заданной таблицы, то это и есть искомое выражение.
Рассмотрим данный конкретный пример:
1) первое заданное выражение X/\Y/\Z= 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 | ||
| А | В |
|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
| 1 | 2 | ||
| А | В |
| 1 В
|
| 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 |
4. Сформулировать ответ. В последнем столбце один «0», соответствующий А, равному «1», и В, равному «0». Получается, что данная функция ложна тогда и только тогда, когда логическая переменная А истинна, а логическая переменная В ложна, что соответствует логической функции СЛЕДСТВИЕ.
Значит данная функция равна логическому следствию переменных А и В: Если А то В. 
.
Пример 2: 
. Определить порядок действий. 
.
Определить размерность таблицы истинности.
«Шапка» таблицы содержит две строки-номера действий и логические операции действий. Количество столбцов определяется количеством логических переменных (их две А, В) и количеством действий (их тоже два).
Количество строк в таблице равно двойке в степени, равной количеству логических переменных – в случае двух переменных получается 4 строки.
1. Поочередно заполнить столбики таблицы в соответствии с логической функцией данного столбца.
| аргументы | 1 | 2 | 3 | 4 | 5 | |
| А | В | А&В |
| 
| 2&3 | 1Ú4 |
| 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 | |
| 1 | 1 | 1 | 0 | 0 | 0 | 1 |
4. Сформулировать ответ. В последнем столбце один «1», соответствуют А, равному В, а «0» - А неравному В. Получается, что данная функция истина, когда А равно В и ложна, когда А не равно В, что соответствует логической функции ТОЖДЕСТВО.
Значит данная функция равна логическому тождеству А и В: А тождественно В. 
.
Дата добавления: 2019-09-08; просмотров: 4785; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!