Докажите что логические выражения равносильны

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

1. Единицы измерения информации и примеры
2. Интуитивное определение алгоритма. Примеры алгоритмов
3. Историко-социологические примеры культурного детерминизма.
4. ЛЕКЦИЯ 6. ПРИМЕРЫ ИСПОЛЬЗОВАНИЯ ФУНКЦИЙ
5. Обоснуйте необходимость обеспечения синергичного эффекта маркетинговых коммуникаций. Приведите примеры интеграции элементов маркетинговых коммуникаций на различных уровнях.
6. Примеры
7. Примеры
8. Примеры
9. Примеры
10. Примеры
11. Примеры

Доказать равносильность формул, используя их таблицы истинности:

а) ;

б) ;

в) .

а) Сравним таблицы истинности для правой и левой частей:

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

б)

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

в)

Исключить возможно большее число скобок:

а) ;

б) .

а) ;

б) .

Восстановить максимальное число скобок, ориентируясь на формальное определение формулы:

а) ;

б) .

а) ;

б) .

а) ;

б) .

а) Удаляя «лишние» скобки, получим:

.

б) Применяя последовательно основные логические законы (III.2.), (II.1.), (I.5.), (IV.8.) и (IV.1.) и удаляя «по пути» скобки, получим:

.

Доказать равносильность формул, используя логические законы:

а);

б) .

а) Преобразуем левую формулу к виду правой формулы, последовательно применив логические законы (I.6.), (I.6.) и (I.2.):

.

б) Применим к левой формуле логические законы (III.1.), (II.2.) и (II.1.):

.

Определить, является ли формула тавтологией, противоречием или ни тем, ни другим:

а) ;

б) ;

в) ;

г) .

а) Приведем формулу к наиболее простому виду, последовательно исключая импликации по логическому закону (III.1.) и убирая двойные отрицания по закону (II.1.):

.

Полученная формула не является логической константой, следовательно, исходная формула не является ни тавтологией, ни противоречием.

б) Применим логические законы (II.2.), (IV.7.) и (IV.2.):

.

Исходная формула – противоречие.

в) Применим (III.1), (I.6), (IV.8) и (IV.1):

Исходная формула не является ни тавтологией, ни противоречием.

г) Применим (III.1), (II.3), (II.2), (II.1), (I.2), (IV.1), (I.5), (IV.3):

Исходная формула не является ни тавтологией, ни противоречием.

Дата добавления: 2014-01-06 ; Просмотров: 1452 ; Нарушение авторских прав? ;

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

Логические выражения называются равносильными, если их итоговые значения совпадают при любых значениях входящих в них логических переменных.

В алгебре логики есть законы, которые позволяют выполнять равносильные преобразования логических выражений. Примеры соотношений, которые отражают эти законы.

Справедливость приведенных законов можно доказать при помощи таблиц истинности: выписать все наборы переменных $A$ и $B$, вычислить на этих наборах значения левой и правой частей доказываемого выражения, сравнить столбцы результатов и убедиться, что они совпали.

Доказать, используя таблицы истинности, что логические выражения равносильны

Составим таблицы истинности для этих выражений

Результирующие столбцы левого и правого выражений совпадают, значит, эти выражения равносильны.

Доказать, при помощи таблиц истинности, что операция эквивалентности равносильна выражению

$А leftrightarrow В$ = ($А cup overline<В>$) & ($overline <А>cup В$)

Результирующие столбцы левого и правого выражений совпадают, значит, эти выражения равносильны.

Попробуй обратиться за помощью к преподавателям

Упростить логическое выражение:

Чтобы проверить, верно ли выполнено задание, надо проверить, являются ли исходное и полученное выражения равносильными, составим таблицы истинности для этих выражений:

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

Задай вопрос специалистам и получи
ответ уже через 15 минут!

Логические выражения, у которых последние столбцы таблиц истинности совпадают, называются равносильными. Для обозначения равносильных логических выражений используется знак «=».

Докажем, что логические выражения равносильны.

Построим сначала таблицу истинности логического выражения (таблица 9).

Таблица 9 – Таблица истинности логического выражения

А

В

Теперь построим таблицу истинности логического выражения
(таблица 10).

Таблица 10 – Таблица истинности логического выражения

А

В

А v В

Значения в последних столбцах таблиц истинности совпадают, следовательно, логические выражения равносильны:

= .

Построение таблиц истинности для сложных выражений

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

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

Если формула содержит три переменные, то возможных наборов значений переменных восемь:

(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1).

Количество наборов для формулы с четырьмя переменными равно шестнадцати и т.д.

Удобной формой записи при нахождении значений формулы является таблица, содержащая кроме значений переменных и значений формулы также и значения промежуточных формул.

1. Составим таблицу истинности для формулы, которая содержит две переменные Xи Y. В первых двух столбцах таблицы запишем четыре возможных пары значений этих переменных, в последующих столбцах — значения промежуточных формул и в последнем столбце — значение формулы. В результате получим таблицу 11:

Таблица 11 – Таблица истинности для формулы с переменными Х и У

Cоставить таблицу истинности сложного логического выражения:
D = неA & (B+C).

А, В, С – три простых высказывания, поэтому:

количество строк = 2 3 +2 = 10 (n=3, т.к. на входе три элемента А, В, С)

количество столбцов (таблица 12):

4) не A – это инверсия А (обозначим Е),

5) B + C – это операция дизъюнкции (обозначим F),

6) D = неA & (B+C), т.е. D = E & F – это операция конъюнкции.

Таблица 12 – Таблица истинности логического выражения D = неA & (B+C)

Логические функции

Любое составное высказывание можно рассматривать как логическую функцию F(Xp X_v . Х_п), аргументами которой являются логические переменные X_v X_v . Х_п (простые высказывания). Функция и аргументы могут принимать только два различных значения; «истина» (1) и «ложь» (0).

Выше были рассмотрены функции двух аргументов: логическое умножение F(A,B) = А & В, логическое сложение F(A,B) = AvB, а также логическое отрицание F(A) = Ā, в котором значение второго аргумента можно считать равным нулю.

Каждая логическая функция двух аргументов имеет четыре возможных набора значений аргументов. По формуле мы можем определить, какое количество различных логических функций двух аргументов может существовать:

Таким образом, существует 16 различных логических функций двух аргументов, каждая из которых задаётся своей таблицей истинности (таблица 13).

Таблица 13 – Таблицы истинности логических функций двух аргументов

Легко заметить, что здесь логическая функция F₂ являеттся функцией логического умножения, F₈ — функцией логического сложения, F₁₃ — функцией логического отрицания для аргумента А и F₁₁ — функцией логического отрицания для аргумента В.

В обыденной и научной речи кроме базовых логических связок «и», «или», «не» используются и некоторые другие: «если….то. », «. тогда и только тогда, когда. » и др. Некоторые из них имеют своё название и свой символ, и им соответствуют определённые логические функции.