Логические операции и таблицы истинности
Оглавление
TOC \o "1-3" \h \z \u Логические операции над высказываниями PAGEREF _Toc472531387 \h 2Логические выражения и таблица истинности PAGEREF _Toc472531388 \h 5Для самостоятельного выполнения PAGEREF _Toc472531389 \h 9
Логические операции над высказываниями1. Отрицание.
Эта логическая операция соответствует в обыденной жизни частице «не».
Определение. Отрицанием высказывания x называется новое высказывание, которое является истинным, если высказывание ложно, и ложным, если высказывание x истинно.
Отрицание высказывания x обозначается и читается не x. Логические значения высказывания модно описать с помощью таблицы, которая называется таблицей истинности:
x
1 0
0 1
Пусть x высказывание. Так как тоже высказывание, то можно образовать отрицание высказывания , то есть высказывание , которое является двойным отрицанием высказывания x. Логические значения высказываний и xсовпадают.
2. Дизъюнкция (логическое сложение).
Эта логическая операция соответствует союзу «или».
Определение. Дизъюнкцией двух высказываний x, y называется новое высказывание, которое считается истинным, если хотя бы одно из высказываний x или y истинно и ложным, если они оба ложны.
Дизъюнкция высказываний x, y обозначается xy и читается «x или y». Логические значения дизъюнкции описываются таблицей истинности:
x y xy
1 1 1
1 0 1
0 1 1
0 0 0
Высказывания x, y называются членами дизъюнкции.
Пример.
x – «5>3», y – «2>4». Тогда xy – «5>3»«2>4» истинно, так как истинно высказывание x.
В алгебре логики союз «или» всегда употребляется в неисключающем смысле. Из определения дизъюнкции и отрицания следует, что высказывание x всегда истинно.
3. Конъюнкция.
Эта логическая операция соответствует союзу «и».
Определение. Конъюнкцией двух высказываний x, y называется новое высказывание, которое считается истинным, если оба высказывания x, y истинны, и ложным, если хотя бы одно из них ложно.
Конъюнкция высказываний x, y обозначается и читается «x и y». Высказывания x, y называются членами конъюнкции. Логические значения конъюнкции описываются следующей таблицей истинности:
x y
1 1 1
1 0 0
0 1 0
0 0 0
Пример.
x – «6 делится на 2», y – «6 делится на 3». Тогда – «6 делится на 2»«6 делится на 3» истинно.
Из определения операции конъюнкции видно, что союз «и» в алгебре логики употребляется в том же смысле, что и в повседневной речи. Но в обычной речи не принято соединять союзом «и» два высказывания, далеких друг от друга по содержанию, а в алгебре логики рассматривается конъюнкция двух любых высказываний.
Из определения операций конъюнкции и отрицания следует, что высказывание всегда ложно.
4. Импликация.
Эта логическая операция соответствует словам «если…,то…».
Определение. Импликацией двух высказываний x, y называется новое высказывание, которое считается ложным, если x истинно, а y ложно, и истинным во всех остальных случаях.
Импликация высказываний обозначается x→y и читается «если x, то y» или «из x следует y». Высказывание x называется условием или посылкой, а высказывание y – следствием или заключением. Высказывание x→y называется следованием или импликацией. Логические значения операции импликации описываются следующей таблицей истинности:
x y x→y1 1 1
1 0 0
0 1 1
0 0 1
Пример.
1) x – «12 делится на 6», y – «12 делится на 3». Тогда импликация x→y – «если 12 делится на 6, то оно делится на 3» истинна, так как истинна посылка x, и истинно заключение y.
2) x – «12 делится на 2 и 3», y – «12 делится на 7». Тогда импликация x→y – «если 12 делится на 2 и 3, то оно делится на 7» ложна, так как условие истинно, а заключение ложно.
Употребление слов «если…,то…» в алгебре логики отличается от употребления их в обыденной речи, когда, как правило, считается, что если высказывание x ложно, то высказывание «если x, то y» вообще не имеет смысла. Кроме того, строя предложение «если x, то y» в обыденной речи всегда подразумевается, что предложение y вытекает из предложения x. Употребление слов «если…, то…» в математической логике не требует этого, так как в ней смысл высказываний не рассматривается.
Импликация играет важную роль в математических доказательствах, так как многие теоремы формулируются в условной форме «если x, то y». Если при этом известно, что x истинно и доказана истинность импликации x→y то истинно и заключение y. В этом случае пишут xy и говорят, что из x следует y. Это классическое правило вывода постоянно используется в математике.
1. Эквиваленция.
Эта логическая операция соответствует словам «тогда и только тогда, когда».
Определение. Эквиваленцией или эквивалентностью двух высказываний x, y называется новое высказывание, которое считается истинным, если оба высказывания x, y либо одновременно истинны, либо одновременно ложны, и ложным во всех остальных случаях.
Эквиваленция высказываний x, y обозначается символом x↔y и читается «для того чтобы x, необходимо и достаточно, чтобы y» или «x тогда и только тогда, когда y». Логические значения операции эквиваленции описываютсяследующей таблицей истинности:
x y x↔y1 1 1
1 0 0
0 1 0
0 0 1
Высказывания x, y называются членами эквиваленции.
Логические выражения и таблица истинности Таблица истинности - таблица, показывающая, какие значения принимает составное высказывание при всех сочетаниях (наборах) значений входящих в него простых высказываний.
Логическое выражение - составные высказывания в виде формулы.
Равносильные логические выражения – логические выражения, у которых последние столбцы таблиц истинности совпадают. Для обозначения равносильности используется знак «=».
Алгоритм построения таблицы истинности:
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.
Пример 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) /\ ¬С
В данной функции три логические переменные – А, В, С
количество строк таблицы = 23 =8
В формуле 3 логические операции.
Расставляем порядок действий
1) А\/ В; 2) ¬С; 3) (AVB) /\ ¬С .количество столбцов таблицы = 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 = ((С \/В) В) /\ (А /\ В) => В.
Построим таблицу истинности этой формулы.
Ответ: формула является тождественно истинной.
Пример 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.
Ответ: 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
Для самостоятельного выполненияПостроить таблицу истинности для выражения
F= (AVB) & (¬AV¬B)
XVY& ¬Z.
Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X,Y,Z. Дан фрагмент таблицы истинности выражения F:
X Y Z F
0 0 0 1
0 0 1 0
0 1 0 1
Какое выражение соответствует F
¬X /\ ¬Y /\ Z
¬X V ¬Y V Z
X V Y V¬Z
X V Y V Z
Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X,Y,Z. Дан фрагмент таблицы истинности выражения F:
X Y Z F
1 0 0 1
0 0 0 1
1 1 1 0
Какое выражение соответствует F?
¬X /\¬Y /\¬Z
X /\ Y /\ Z
X V Y V Z
¬ X V¬Y V¬Z