Отправляет email-рассылки с помощью сервиса Sendsay

Информат - алгоритмическое и математическое мышление

Рассылка закрыта

При закрытии подписчики были переданы в рассылку "физика YES" на которую и рекомендуем вам подписаться.

Вы можете найти рассылки сходной тематики в Каталоге рассылок.

←   Март 2011   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Автор
ss77_ss77@mail.ru

Статистика

1.523 подписчиков
+1 за неделю
←   Все выпуски   →

Информат - алгоритмическое и математическое мышление


Лого 

 ИНФОРМАТ 

развитие алгоритмического и математического мышления


--

Здравствуйте все интересующиеся развитием алгоритмического и математического мышления!

-- --

Новости

Вот и прошёл праздник 8 Марта. Завтра последний день получить от меня подарок.

 А сегодня разбор задачи и одновременно загадка.

Сегодня разберём задачу «ЕГЭ по информатике 2011 демо B10».

Сколько различных решений имеет уравнение:

((J -> K) -> (M & N & L)) & ((J & ~K) -> ~(M & N & L)) & (M -> J) = 1

где J, K, L, M, N - логические переменные?

В ответе не нужно перечислять все различные наборы значений J, K, L, M и N, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

Подобные задачи относятся к разделу математики под названием "Логика". Но в едином государственном экзамене они отнесены к информатике. Поэтому задача опубликована здесь.
Есть программискский способ решения этой задачи. Попробуйте перебрать все решения заданного уравнения и подсчитать их количество.

Решение

Используем формулу A->B = ~A v B

Рассмотрим одну подформулу:
((J & ~K) -> ~(M & N & L)) = ~(~J v K) -> ~(M & N & L) = ~(J -> K) -> ~(M & N & L) = ~~(J -> K) v ~(M & N & L) = (J -> K) v ~(M & N & L) = (M & N & L) -> (J -> K)

Получим изменённое уравнение:
((J -> K) -> (M & N & L)) & ((M & N & L) -> (J -> K)) & (M -> J) = 1

Используем (A->B) & (B->A) = A <-> B
((J -> K) -> (M & N & L)) & ((M & N & L) -> (J -> K)) = (J -> K) <-> (M & N & L)

Получим уравнение эквивалентное исходному:
((J -> K) <-> (M & N & L)) & (M -> J) = 1

Множество решений уравнения равно множеству решений системы уравнений:
(J -> K) <-> (M & N & L) = 1
M -> J =1

Или объединению множеств решений двух систем:
J -> K = 1
M & N & L = 1
M -> J = 1
 		и J -> K = 0
M & N & L = 0
M -> J = 1

Первая система имеет единственное решение:
J=K=M=N=L=1
И оно не подходит для второй системы.
Значит, у систем нет одинаковых решений (не пересекаются) и количества их решений можно просто сложить.

Вторая система имеет 7 решений:
J -> K = 0 — 1 решение (J=1 K=0)
M & N & L = 0 — 8-1=7 решений
M -> J = 1 — 2 решения (M-любой), они входят в множество решений предыдущего уравнения.
Всего: 1*7 = 7.

Итого: 7+1 — 8 решений


А теперь загадка?
Найти более короткий способ решения этой задачи.
Ответы присылайте на мой адрес.

Вячеслав Викторович Пупышев

Подарки на 23 февраля и 8 марта! Подробности на сайте.

Курсы

Развитие алгоритмического мышления.    Хочу изучить      Блок в подарок

Базовое программирование.    Хочу изучить

Работа с калькулятором.    Хочу изучить

Подготовка к ЕГЭ по информатике. Хочу получить более 80 баллов

  -- 03.03.2011    Добавлена задача по программированию "ЕГЭ по информатике 2011 демо B10". Перейти
20.02.2011    Пупышев Вячеслав Викторович послал очередную информацию через Subscribe.ru. Перейти
19.02.2010    К праздникам 23 февраля и 8 марта всем, кто проходит или начнёт проходить курсы - подарок. Перейти
07.02.2011    Добавлены тесты для задачи районной олимпиады по программированию "ЕГЭ C4". Перейти
19.01.2011    Добавлена задача по математике "Шел Кондрат в Ленинград". Перейти
12.01.2011    Курс: Базовое программирование. Небольшие изменения на страничке. Перейти
06.01.2011    Курс: Развитие алгоритмического мышления. Обновлён ознакомительный блок 2.1 Перейти
30.12.2010    К Новому Году на страницу игр добавлена игра "Коровий марафон зимой". Перейти
13.11.2010    В разделе юмор добавлена картинка "Реальное копирование". Перейти
09.11.2010    Подготовка к ЕГЭ по информатике. Перейти
03.10.2010    Добавлена статья "Отдых для глаз". Перейти
08.09.2010    Курсы: Реальное программирование. Перейти
07.09.2010    Интересный факт: Y-хромосома и палиндромы. Перейти
Copyright (C) 2010-2011 Информат
В избранное