Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Задача по математической логике  (Прочитано 11521 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Olegator
Команда клуба

ru
Offline Offline
Пол: Мужской

« : 22-05-2006 12:51 » 

И.Л. Никольская. "Математическая логика" упр. 21, стр. 34.
Упростите следующую, инструкцию: "Подчеркивайте числа, которые одновременно кратны трем, оканчиваются нулем и имеют
сумму цифр, большую 37. Подчеркивайте также те числа, которые
не делятся на 3, оканчиваются нулем н имеют сумму цифр, не превосходящую 37. Кроме того, подчеркивайте числа, которые оканчиваются нулем, делятся на 3 и сумма цифр которых не более 37, а также числа, оканчивающиеся нулем, с суммой цифр, большей 37, и не кратные трем. И наконец, подчеркивайте числа, кратные трем, не оканчивающиеся нулем и имеющие сумму цифр, превосходящую 37".

Если обозначить:
Х1-кратны трём
Х2-оканчивается нулём
Х3-сумма цифр > 37

то получится следующая формула:
(X1^X2^X3)v(notX1^X2^notX3)v(X1^X2^notX3)v(notX1^X2^X3)v(X1^notX2^X3)
Решение:
1. Сначала по закону идемпотентности (ХvX=X) делаем так:
(X1^X2^X3)v (X1^X2^X3)v (X1^X2^X3)v (notX1^X2^notX3)v(X1^X2^notX3)v(notX1^X2^X3)v(X1^notX2^X3)
2. Затем по закону склеивания (X^Y)v(notX^Y)=Y получаем:
 (X1^X2)v(X1^X3)v(X2^X3)v(notX1^X2^notX3)
До этого момента вроде всё верно. И может быть это уже ответ. Но я продолжил дальше:
3. По закону дистрибутивности (X^Y)v(X^Z)=X(YvZ):
(X1^X2)v(X2^X3)=X2^(X1vX3)
4. По закону де Моргана (notX^notY)=not(XvY):
(notX1^X2^notX3)=X2^(not(X1vX3))
5. Получается так:
(X1^X3)v(X2^(X1vX3))v(X2^(not(X1vX3)))
6. По закону склеивания:
(X1^X3)vX2
И тут у меня сомнения. Может где-то с 3 по 6 пункт я допустил ошибку.
« Последнее редактирование: 22-05-2006 12:55 от Olegator » Записан
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #1 : 22-05-2006 14:04 » 

Olegator, если с точки зрения программирования, то можно удобоваримее сделать:
У тебя даны 5 вариантов комбинаций трех параметров (по два варианта на параметер). Всего комбинаций может быть 2^3 = 8. Если разбить по битам (так просто будет удобнее нумеровать варианты), то заданы: 7, 2, 3, 6 и 5. Нужно провести для каждого числа три теста и по результату определить номер, а по номеру решить - подчеркивать или нет.
Замечу так же, что если число оканчивается на 0, то по условиям его всегда нужно подчеркивать.
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #2 : 22-05-2006 14:34 » 

Olegator, выдели общее из первых четырех, а потом и упрощать ничего не надо должно получиться (X1^X3^notX2)vX2
Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Sands
Помогающий

ua
Offline Offline

« Ответ #3 : 22-05-2006 19:47 » 

Sla, по-моему, (X1^X3^notX2)vX2 еквивалентно (X1^X3)vX2
Записан
Olegator
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #4 : 23-05-2006 20:42 » 

Sla, по-моему, (X1^X3^notX2)vX2 еквивалентно (X1^X3)vX2
Верно. Значит я не ошибся.
Записан
Olegator
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #5 : 09-07-2006 00:49 » 

Ещё одна задача из того же источника:
Цитата
Докажите, что число попарно неравносильных формул с переменными Х1, Х2,...,Хn равно 2(2n)

1. И тут не понятно, что значит число попарно неравносильных формул.
Т.е. допустим "F1 не равносильно F2" и "F3 не равносильно F4". Сколько тут попарно неравносильных формул? 2 или 4?

2. Как я понял при составлении всего множества формул, когда мы получаем дизъюнкцию конъюнкций, количество конъюнкций получается равным (2n). Как это доказывается, пока не знаю.

И теперь что значит 2(2n)
« Последнее редактирование: 09-07-2006 01:27 от Olegator » Записан
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #6 : 09-07-2006 09:46 » new

Попарно неравносильные означают, что для любой формулы во множестве формул на общем множестве переменных нет равносильной ей. Любые две формулы достаточно свести к их полным дизъюнктивной или конъюнктивной нормальным формам (ДНФ, КНФ), чтобы установить их равносильность или неравносильность. Можно и по таблицам истинности проверять.

Попытаюсь объяснить наглядно. В случае N переменных имеется 2^N различных наборов значений этих переменных: если выписать в таблице по столбцам переменые X1...XN, то их значения, состоящие из 1 и 0 займут 2^N различных строк. В этой же таблице можно ввести колонку результата F, имеющую 2^N значений. Так как неравносильные формулы дают различный результат, получаем, что каждая формула даёт набор из M=2^N значений. Количество таких наборов 2^M. Таким образом, имеем количество неравносильных формул 2^(2^N).

Пример для N=2.

Имеем 2^N наборов значений переменных (в данном случае 4).
Код:
X1 X2  F
 0  0
 0  1
 1  0
 1  1

В этом случае F может принимать следующие возможные значения:
Код:
F
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1
Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines