Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Свидетельство о публикации

Автоматическая выдача свидетельства о публикации в официальном СМИ сразу после добавления материала на сайт - Бесплатно

Добавить свой материал

За каждый опубликованный материал Вы получите бесплатное свидетельство о публикации от проекта «Инфоурок»

(Свидетельство о регистрации СМИ: Эл №ФС77-60625 от 20.01.2015)

Инфоурок / Информатика / Конспекты / Мастер-класс по подготовке к ЕГЭ по информатике. Логика.
ВНИМАНИЮ ВСЕХ УЧИТЕЛЕЙ: согласно Федеральному закону № 313-ФЗ все педагоги должны пройти обучение навыкам оказания первой помощи.

Дистанционный курс "Оказание первой помощи детям и взрослым" от проекта "Инфоурок" даёт Вам возможность привести свои знания в соответствие с требованиями закона и получить удостоверение о повышении квалификации установленного образца (180 часов). Начало обучения новой группы: 28 июня.

Подать заявку на курс
  • Информатика

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

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

27.84 КБ Б15.docx
1.74 МБ Логические уравнения и системы_inf-2011-14.pdf

Выбранный для просмотра документ Б15.docx

библиотека
материалов

http://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

x1→x2

0

0

1

0

1

1

1

0

0

1

1

1

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

x1

x2

x3

x4

0

0

0

0

0

0

0

1

0

0

1

1

0

1

1

1

1

1

1

1

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

2 способ

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

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

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

Если x1 → x2=0:

x1

x2

x3

x4

1

0

0

0

1

0

0

1

1

0

1

0

1

0

1

1

x1=1, x2=0, 

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

Если x2 → x3=0:

x1

x2

x3

x4

0

1

0

0

0

1

0

1

1

1

0

0

1

1

0

1

x2=1, x3=0,

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

Если x3 → x4=0:

x1

x2

x3

x4

0

0

1

0

0

1

1

0

1

0

1

0

1

1

1

0

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

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

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

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

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

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

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

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

y1

y2

y3

y4

0

0

0

0

0

0

0

1

0

0

1

1

0

1

1

1

1

1

1

1

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

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

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

y1

y2

y3

y4

   
   

x1

x2

x3

x4

0

0

0

0

0

0

0

0

0

0

0

1

0

0

0

1

0

0

1

1

0

0

1

1

0

1

1

1

0

1

1

1

1

1

1

1

1

1

1

1

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

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

y1

y2

y3

y4


    
  

x1

x2

x3

x4

0

0

0

0

0

0

0

0

0

0

0

1

0

0

1

0

0

1

1

0

0

1

1

0

1

1

1

0

1

1

1

1

1

1

1

1

1

1

1

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

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

y1

y2

y3

y4


   

x1

x2

x3

x4

0

0

0

0

0

0

0

0

0

0

0

1

0

0

0

1

0

0

1

1

0

0

1

1

0

1

1

1

0

1

1

1

1

1

1

1

1

1

1

1

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

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

y1

y2

y3

y4


   

x1

x2

x3

x4

0

0

0

0

0

0

0

0

0

0

0

1

0

0

0

1

0

0

1

1

0

0

1

1

0

1

1

1

0

1

1

1

1

1

1

1

1

1

1

1

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

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

y1

y2

y3

y4


   

x1

x2

x3

x4

0

0

0

0

0

0

0

0

0

0

0

1

0

0

0

1

0

0

1

1

0

0

1

1

0

1

1

1

0

1

1

1

1

1

1

1

1

1

1

1

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

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

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

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

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



Подайте заявку сейчас на любой интересующий Вас курс переподготовки, чтобы получить диплом со скидкой 50% уже осенью 2017 года.


Выберите специальность, которую Вы хотите получить:

Обучение проходит дистанционно на сайте проекта "Инфоурок".
По итогам обучения слушателям выдаются печатные дипломы установленного образца.

ПЕРЕЙТИ В КАТАЛОГ КУРСОВ

Краткое описание документа:

Урок 1. Базовые знания математической логики, логические элементы и таблицы истинности.

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

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

 

Урок 2. Порядок выполнения логических выражений. Создание логических схем и таблиц истинности.

Во втором уроке рассматриваем  порядок выполнения логических операций. Берем конкретный  пример, логическую формулу, показываем аналогию с операциями в математике.  Далее рисуем логическую схему, состоящую  из блоков рассматриваемой формулы.  Далее рассматриваем формулу, с помощью которой мы можем рассчитать количество возможных событий, которые мы можем получить, подавая на входы нашей схемы различные сигналы.  А затем составляем таблицу истинности. Используя полученную логическую схему и базовые таблицы истинности показываем,  как просто определить результат события, которое наступает при определенной подаем сигналов на входы схемы.  Рассказываем о существовании полных и неполных таблиц истинности.

 

Урок 3. Решаем логические выражения через построение таблиц истинности. В третьем уроке рассматриваем пример задания, для решения которого необходимо уметь составлять таблицы истинности.  Все действия описываем по шагам, для того, что бы объяснение было максимально понятно.  Повторяем порядок действий, т.е. приоритет логических операций.  Показываем, как удобнее пользоваться таблицами истинности для решения логических выражений. Для повышения эффективности решения  рассматриваем выигрышные  стратегии  решения подобных заданий.

 

Урок 4. Основные законы математической логики.

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

 

Урок 5. Математическая логика. Пример решения задания.

Рассматриваем еще одно задание на проверку знаний основ логики. В нем нужно определить при каких значениях Х истинно логическое высказывание.  Опять же напоминаем, что при решении подобных заданий, помнить порядок логических операций и знать их таблицы истинности.  Выполняем решение и поясняем каждое наше действие.

 

 

Автор
Дата добавления 21.04.2015
Раздел Информатика
Подраздел Конспекты
Просмотров526
Номер материала 490430
Получить свидетельство о публикации
Похожие материалы

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