Преподавателю
Информатика
Мастер-класс по подготовке к ЕГЭ по информатике. Логика

Мастер-класс по подготовке к ЕГЭ по информатике. Логика

Урок 1. Базовые знания математической логики, логические элементы и таблицы истинности. В первом уроке мы познакомимся с основными понятиями логики. Логические элементы, логические выражения, таблицы истинности правила выполнения логических выражений и принципы построения логических схем. Рассматриваем конъюнкцию, дизъюнкцию, инверсию (отрицание) и импликацию (следование), составляем для них таблицы истинности. Показываем, как эти логические элементы мы можем отобразить на схеме и при записи л...

Раздел	Информатика
Класс	-
Тип	Конспекты
Автор	Максимова И.В.
Дата	12.03.2015
Формат	zip
Изображения	Нет

Поделитесь с коллегами:

infoegehelp.ru/index.php?option=com_content&view=article&id=460&Itemid=77

Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, y1, y2 y3, y4, которые удовлетворяют всем перечисленным ниже условиям?
(x1 → x2) /\ (x2 → x3) /\ (x3 → x4) = 1
(¬y1 \/ y2) /\ (¬y2 \/ y3) /\ (¬y3 \/ y4) = 1
(y1 → x1) /\ (y2 → x2) /\ (y3 → x3) /\ (y4 → x4) = 1
В ответе не нужно перечислять все различные наборы значений переменных x1, x2, x3, x4, y1, y2 y3, y4, при которых выполнена данная система равенств.
В качестве ответа Вам нужно указать количество таких наборов.

Ответ: 15

Решение:

Преобразуем систему уравнений к виду:

(x1 → x2) /\ (x2 → x3) /\ (x3 → x4) = 1 (1)

(y1 → y2) /\ (y2 → y3) /\ (y3 → y4) = 1 (2)

(y1 → x1) /\ (y2 → x2) /\ (y3 → x3) /\ (y4 → x4) = 1 (3)

Розовым выделено уравнение, которое было преобразовано. ¬y1 \/ y2=y1 → y2. Аналогично и для остальных частей данного уравнения.

Решим уравнение (1).

1 способ

Уравнение (1) содержит импликации (→), связанные конъюнкцией (/\). Соответственно, чтобы уравнение было истинно, все входящие импликации должны быть истинны:

x1 → x2=1,

x2 → x3=1,

x3 → x4=1.

Таблица истинности для импликации на примере x1 → x2:

x1→x2

Розовым выделена комбинация, когда импликация ложна. Видно, что в ней идут подряд "1" и "0". Выпишем комбинации для x1x2x3x4, в которых не встречается подряд "1" и "0", чтобы импликации x1 → x2, x2 → x3, x3 → x4 не были равны 0-ю.

Получили 5 комбинаций.

2 способ

Решим методом от противного. Рассмотрим случаи, когда уравнение (x1 → x2) /\ (x2 → x3) /\ (x3 → x4)=0.

Импликация ложна, когда посылка истинна, а следствие ложно. Таблица истинности приведена выше:

Исходя из этого определим случаи, когда импликация ложна.

Если x1 → x2=0:

x1=1, x2=0,

x3 и x4 - 0 или 1, поэтому они дают 2²=4 комбинации.

Если x2 → x3=0:

x2=1, x3=0,

x1 и x4 - 0 или 1, поэтому они дают 4 комбинации.

Если x3 → x4=0:

x3=1, x4=0, x1 и x2 - 0 или 1, поэтому они дают 4 комбинации.

Получили 4*3=12 комбинаций.

Также нужно учеть повторные комбинации. В данном случае повторная комбинация одна: 1010. В таблицах выше такая комбинация выделена синей рамкой. Она встретилась 2 раза, поэтому общее число комбинаций с учетом повторов: 12−1=11.

Мы решали уравнение методом от противного. Теперь перейдем к исходному уравнению.

Общее число комбинаций при 4-х переменных: 2⁴=16. 16-11=5 комбинаций.

Перейдем к уравнению (2):

(y1 → y2) /\ (y2 → y3) /\ (y3 → y4) = 1.

Это уравнение содержит переменные y1, y2, y3, y4, которые не связаны с уравнением (1). Уравнения (1) и (2) независимы друг от друга. Но вид уравнения (2) аналогичен виду уравнения (1), которое мы решили выше. Поэтому получаем 5 комбинаций.

Добавим к системе уравнение (3):

(y1 → x1) /\ (y2 → x2) /\ (y3 → x3) /\ (y4 → x4) = 1

Выпишем рядом решения уравнений (1) и (2)

Будем решать систему уравнений методом от противного. Уравнение (3) равно 0-ю.

y1 → x1=0: y1=1, x1=0

Получили 4 комбинации.

y2 → x2=0: y2=1, x2=0. Строку 1111 (y1y2y3y4) не берем во избежание повторов.

Получили 3 комбинации.

y3 → x3=0 y3=1, x3=0. Строки 1111, 0111 (y1y2y3y4) не берем во избежание повторов.

Получили 2-е комбинации.

y4 → x4=0 y4=1, x4=0. Строки 1111, 0111, 0011 (y1y2y3y4) не берем во избежание повторов.

Получили 1-у комбинацию.

Всего комбинаций: 4+3+2+1=10.

Мы решали систему уравнений методом от противного. Теперь перейдем к исходной системе.

Общее число комбинаций: 5*5=25. Уравнения (1) и (2) дают по 5 независимых комбинаций.

25-10=15 комбинаций.

загрузить