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

⇐ ПредыдущаяСтр 6 из 9Следующая ⇒

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

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

A	B

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

A	B	AVB

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

Задачи и упражнения

Задание №1.

Доказать с помощью таблиц истинности свойства импликации, эквивалентности разделительной конъюнкции.

Задание №2.

Формализуйте приведенные ниже высказывания и постройте для них таблицы истинности:

X= «если одно слагаемое делится на 3 и сумма делится на 3, то и другое слагаемое делится на 3»

Y= «если одно слагаемое делится на 3, а другое не делится на 3, то сумма не делится на 3»

Убедитесь, что результирующие столбцы совпадают.

Задание №3.

Построить таблицы истинности для логических выражений а) и б), если А=1, В=0

а) (AV )& B
б)A& (AVB)& (BV ).

Задание №4.

Упростите логическую формулу и определите ее истинность:

(Аà B)& (Bà (CVA))& (Bà (A& C))& (Bà A).

Задание №5.

Постройте таблицы истинности для формул:

((CVB)à B)& (A& B)à B;

((CVB)à B)& (AvB)à B.

ЛОГИЧЕСКИЕ ФУНКЦИИ

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

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

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

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

Аргументы

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

F₁

F₂

F₃

F₄

F₅

F₆

F₇

F₈

F₉

F₁₀

F₁₁

F₁₂

F₁₃

F₁₄

F₁₅

F₁₆

Здесь логическая функция -функцией логического сложения, -функцией логического отрицания для аргумента А и -функцией логического отрицания для аргумента В.

Задачи и упражнения

Задание №1.

Доказать, используя таблицы истинности, что операция эквивалентности А< < => > В равносильна логическому выражению (AV )& ( VB).

Задание №2.

По заданной таблице истинности записать логическую функцию:

A	B	С	F (a, b, c)

Упростить логическую функцию. Показать правильность преобразований с помощью таблицы истинности. Составить логическую схему.

Задание №4.

Задана таблица истинности записать логическую функцию:

A	B	С	F (a, b, c)

ЛОГИЧЕСКИЕ ЗАКОНЫ И ПРАВИЛА ПРЕОБРАЗОВАНИЯ

ЛОГИЧЕСКИХ ВЫРАЖЕНИЙ

Закон тождества.

Всякое высказывание тождественно самому себе:

А=А

Закон противоречия.

Высказывание не может быть одновременно истинным и ложным.

Если высказывание А истинно, то его отрицание не А должно быть ложным. Следовательно, логическое произведение высказывания и его отрицания должно быть ложно:

А& A=0

Закон исключительного третьего.

Высказывание может быть либо истинным, либо ложным, третьего не дано. Это означает, что результат логического сложения высказывания и его отрицания всегда принимает значение «истина»:

AV =1

Закон двойного отрицания.

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

Закон де Моргана:

& B

Важное значение для выполнения преобразований логических выражений имеют законы алгебраических преобразований. Многие из них имеют аналоги в обычной алгебре.

Закон коммутативности.

В алгебре высказываний можно менять местами логические переменные при операциях логического умножения и логического сложения:

Логическое умножение	Логическое сложение
А& B=B& A	АVB=BVA

Закон ассоциативности.

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

Логическое умножение	Логическое сложение
(А& B)& C=A& (B& C)	(АVB)VC=AV(BVC)

Закон дистрибутивности.

В алгебре высказываний можно выносить за скобки как общие множители, так и общие слагаемые:

Дистрибутивность умножения относительно сложения	Дистрибутивность сложения относительно умножения
(А& B)V(A& C)=A& (BVC)	(АVB)& (AVC)=AV(B& C)

Рассмотрим в качестве примера применения законов логики преобразование логического выражения. Пусть нам необходимо упростить логическое выражение:

(A& B)V(A& )

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

(A& B)V(A& )=A& (BV )

По закону исключенного третьего BVB=1, следовательно:

A& (BV )=A& =1

Преобразование логических выражений.

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

Пример 1. Упростить следующую логическую формулу:

Решение:

à =(AvB)& ( )=(AvB)& (BvC)=(AvB)& Bv(AvB)& C=A& BvBvA& CvB& C=B& (Av1)vC& (AvB)=BvA& CvB& C=(B& (1vC)vA)& C=(BvA)& C.

Пример 2. Переведите к виду логической формулы высказывание: «Неверно, что если погода пасмурная, то дождь идет тогда и только тогда, когда нет ветра».

Решение: определим следующие простые высказывания:

П – «пасмурная погода»; Д – «идет дождь»; В – «дует ветер».

Тогда соответствующее логическое выражение запишется так: Пà (Д< -> В).

Пример 3. Кто из учеников A, B, C играет, а кто не играет в шахматы, известно следующее:

а) если А и В играет, то С не играет

б) если В не играет, то играют С и В;

в) С играет?

Решение. Определим следующие высказывания:

А- «ученик А играет в шахматы»;

В- «ученик В играет в шахматы»;

С- «ученик С играет в шахматы»;

D- «ученик D играет в шахматы»;

Запишем сложные высказывания, выражающие известные факты:
а) (AvB)à C

б) Bà C& B

в) С

Запишем производные указанных сложных высказываний:

((AvB)-> C)& ( B à C& D)& C

Упростим эту формулу:

((AvB)à C)& ( Bà C& D)& C=(((AvB)vC)& (BvC& D)& C=((A& B)vC)& (BvC& D)& C=A& B& C& D=1

Отсюда А=0, В=0, С=1, D=1.

Ответ: в шахматы играют ученики C и D, а ученики А и В не играют.

Задачи и упражнения:

Задание №1.

Доказать справедливость первого & B и второго VB законов де Моргана, используя таблицы истинности.

Задание №2.

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

а) (AVA)& B;

б) A& (AVB)& (BV ).

Задание №3.

Упростите логическую формулу и определите ее истинность:

(Aà B)& (Bà (А& С))& (Вà А).

Задание №4.

Определите значение формул:

((CvB) à B)& (A& B) à B;

((CvB) à B)& (AvB) à B.

Задание №5.

Заданы логические функции:

Необходимо упростить эти функции и проверить, являются ли они тождественными.

Задание №6.

Переведите на язык логических выражении следующие высказывания:

1. «Я поеду в Москву, и если встречу там друзей, то мы интересно проведем время».

2. «Если будет солнечная погода, то ребята пойдут в лес, а если будет пасмурная погода, то ребята пойдут в кино ».

3. «Наверное, что если дует ветер, то солнце светит только тогда, когда нет дождя».

4. «Если урок информатики будет интересным, то никто из школьников- Миша, Вика, Света – не будет смотреть в окно».

Задание №7.

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

1. (A& B)v( vB)v(СvB)

2. (A& )v(A& B)v(A& )

3. (A& B)v(A& )v( & C)

4. (AvB)& ( vA)& (Cv )

5. ( & B)v(A& B)v(B& )

6. (B& )v(B& C)v(A& B)

7. (BvC)& (Bv )& (Av )

8. (Bv )v(B& C)v( & B)

9. (BvC)& ( vC)& (Av )

10. (B& C)v(B& )v( & A)

11. (C& )v(C& B)v( & C)

12. (Cv )& (CvB)& ( vC)

13. (C& B)v(C& )v(A& )

Задание №8.

Три друга обсуждают истории Нового года и каждый сказал следующие:

· Празднование Нового года с 1 января установили во Франции в 45 году до Рождество Христова (Юлием Цезарем)

· Празднование Нового года с 1 января установили римляне в 1659 году указом Карла IX.

· Празднование Нового года с 1 января установили во II веке и не французы

Оказавшийся рядом знаток истории сказал, что каждый из них прав только в одном из двух высказанных предложений.

Где и какое время было установлено празднование Нового года с 1 января?

Задание №9.

На Новогодний праздник три друга- Евгений, Николай, Алексей, выбрали себе костюмы трех богатырей: Ильи Муромца, Алеши Поповича, Добрыни Никитича.

Известно что:

· Евгений- самый высокий.

· Выбравший костюм Добрыни Никитича меньше ростом, чеи выбравший костюм Ильи Муромца.

· Алексею не подошел костюм Добрыни Никитича.

· Ни у одного из друзей имя не соответствует с именем богатырей, выбранных костюмов.

Какой костюм выбрал каждый из друзей?

Задание №10.

Известно, что на одной двери надпись истина, а на другой ложь.

Если надпись на первой двери – «за этой дверью есть подарок», а на второй двери – «подарок за обоими дверьми», то:

1) Подарок за обоими дверьми;

2) Подарок только за второй двери;

3) Подарка нет ни за одной дверью;

4) Подарок только за первой дверью;

5) Определено место подарка установить нельзя.

6) Выберите правильный ответ.

Задание №11.

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

Сергей-первый, Руслан-второй;

Сергей-второй, Руслан-третий;

Денис-второй, Руслан-четвертый.

Известно, что в каждом ответе только одно утверждение истинно. Как распределить места?

Задание №12.

Алеша, Боря и Гриша нашли в земле старинный сосуд. Расматривая удивительную находку, каждый высказал по два предложения:

Алеша: «это сосуд греческий и изготовлен в 5 веке».

Боря: «это сосуд финикийский и изготовлен в 3 веке».

Гриша: «это сосуд не греческий и изготовлен в 4 веке».

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

Где и в каком веке изготовлен сосуд?

⇐ Предыдущая 1 2 3 4 567 8 9 Следующая ⇒