@light-revan

Очень прошу помочь с 2 функциями- для каждой необходмио Таблицу истинности построить + СДНФ и СКНФ + упростить СДНФ и СКНФ. Сам делал, но тестирующая система говорит, что неверно, бьюсь давно. Онлайн - калькуляторами проверить сложно - все дают разные ответы когда упрощаешь СДНФ и СКНФ. Тема недостаточно раскрыта для меня - мало практики на классных занятиях (1 пример простенький разобрали)
1) F(X,Y,Z) = X⇔Y&¬X⊕ZvX&Y
2) F(X,Y,Z) = X&Y&¬X⇔ZvX&Y

0

@3D Homer

Напишите сравнительный приоритет операций, таблицу истинности, СДНФ и СКНФ. Также напишите, на что жалуется тестирующая система.

0

@light-revan

Сейчас проверил в онлайн именно таблицу и СДНФ и СКНФ, совпало решение:
2)
10101000 - --- здесь с калькулятором совпало
СДНФ: ¬X¬Y¬Z∨¬X Y¬Z∨X ¬Y ¬Z - --- здесь с калькулятором совпало
СКНФ: (X∨Y∨¬Z)(X∨¬Y∨¬Z)(¬X∨Y∨¬Z)(¬X∨¬Y∨Z)(¬X∨¬Y∨¬Z) - --- здесь с калькулятором совпало

Тестирующая система не начисляет баллы за ответы - так она себя бывает ведет; но в чем именно правильно решение или нет - неизвестно. Иногда начисляет через сутки)) Статус ответов верно или нет - неизвестно))
Упрощаю сам СДНФ и СКНФ, есть ли здесь что?:
СДНФ: ¬X¬Y¬Z∨¬X Y¬Z ∨X ¬Y ¬Z склеивание
¬X¬Z v X¬Y¬Z раскладываю на слагаеимы
¬XX + ¬X¬Y + ¬X¬Z + X¬Z + ¬Y¬Z + ¬Z¬Z
¬X¬Y + ¬X¬Z + ¬Z поглощение
¬Z + ¬X¬Y


СКНФ: применяю к 1 и 2 коънюнкции склеивание и к 3 и 5 тоже склеивание, получаю
(X + ¬Z)(¬X + ¬Z)(¬X + ¬Y + Z) снова склеивание
¬Z *(¬X + ¬Y + Z) раскрываю скобки
¬Z¬X + ¬Z¬Y + ¬ZZ = ¬X¬Z + ¬Y¬Z

верно ли?

0

@3D Homer

Если вы применяете дистрибутивность дизъюнкции относительно конъюнкции к первому выражению, то будет (¬x v x)(¬x v ¬y)(¬x v ¬z)...(¬z v ¬z).

Я бы сделал так.


(дублируем первую конъюнкцию)


Порядок действий проще всего увидеть на карте Карно.

1

@light-revan

спасибо, дизъюнкцию сложных конъюнкций не разбирали по распред. закону, только когда --- x(yvz)=(x+y)*(x+z)... Продолжил ваше решение и получил верный ответ!

(дублируем первую конъюнкцию)

Такую штуку и Карно не изучали, может позже - далее по курсу. Спасибо!
Сейчас попробую в Тест. системе

А 1) пример постараюсь сам, но сюда отпишу

Добавлено через 17 часов 17 минут
по 1) примеру:

=10010111
СДНФ

далее упростить нельзя, как мне кажется?
СКНФ
раскрываю 1 и 2 скобки
теперьв 1 скобках: 1кон = Х, 2 и 4 = Х, 3 и 7 = Х, 5 = 0, 9 = 0, тогда

далее раскрываю оставшиеся:

в 1 кон = 0, 6ой = 0, 9ой = 0, тогда
4 и 5 кон = YZ, тогда


дальше, скорее всего, можно упростить, но не знаю как, помогите

ПыСЫ: Тестовая система на прошлый ответ балов не начислила пока что,

Добавлено через 8 минут
+ потерял в последних 2 строчках

0

@3D Homer

Вообще говоря, пока вы не внесете ясность с приоритетом операций, как я просил в сообщении 2, дальнейшее — это просто угадывание. Исходный формулы можно разобрать множеством способов.

0

@light-revan

2) ¬X; X*Y; X*Y*¬X; X*Y; Z+X*Y; X*Y*¬X <=> Z+X*Y
это требуется, правильно понимаю?

0

@3D Homer

Под приоритетом операций я имею в виду порядок исполнения операций: например, скобки, возведение в степень, умножение, деление, сложение, вычитание. Со второй формулой более-менее понятно. В первой формуле непонятен порядок исполнения ⊕, v и ⇔. Поскольку в формуле используется и ⊕, и v, я против того, чтобы обычную дизъюнкцию обозначать через +. Кроме того, я бы рекомендовал пропускать конъюнкцию, аналогично умножению в арифметике, для упрощения записи.

0

@light-revan

Ок:
1) F(X,Y,Z) = X⇔Y&¬X⊕ZvX&Y


1.
2.
3.
4.
5.
6.

0

@3D Homer

Из того, что вы написали, следует, что исключающее ИЛИ имеет более высокий приоритет, чем обычное ИЛИ, а эквивалентность имеет наименьший приоритет.

В LaTeX'е ⊕ набирается командой \oplus, а v — \vee.

С этим я согласен.

Мне кажется, это минимальная КНФ. Раскрывая скобки, вы только придете к ДНФ, которую вы уже рассмотрели.

1

@light-revan

Да, Исключ_ИЛИ и ИЛИ по лекции одинаковый приоритет, насколько верно записал; а эквивалентность сразу после них идет по приоритезации.

0

@light-revan

Проверьте пожалуйста, верно ли упрощаю:
СДНФ:
---сперва склеивание 1 и 3
---здесь поглощение


СКНФ:
--- здесь склеивание 1 и 5
--- затем раскрываю 1 и 2 скобку
взаимно сокращаются ---
--- остается раскрыть скобки
--- последнюю конъюнкцию убираю

0

@3D Homer

.

.

И мне все-таки непонятно, почему вы КНФ превращаете в ДНФ. Так сказано в условии задачи?

1

@light-revan

Не, просто по ходу упрощения "превращается в ДНФ". Это вполне может быть при упрощении - сказал нам преподаватель, т.е. могут совпасть и пойдет в ответ Тестсистемы. Лишь поэтому я так делаю.

Смотрю у меня с самого начала неверный ход, как поступить тогда? Просто дистрибуцию применять?

0

@3D Homer

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

В сложных выражениях я не вижу замене картам Карно или эквивалентному методу. По ним затем можно записать цепочку преобразований, но они показывают, что с чем нужно склеивать. Есть сайты, которые строят карты, например, здесь и здесь.

В с помощью этих сайтов у меня получается . В получается .

Можно также воспользоваться WolframAlpha. Столбец в таблице истинности там нужно записывать в обратном порядке, то есть от (1, 1, 1) к (0, 0, 0). Таким образом, запрос BooleanFunction[{1,0,1,1,0,0,0,0}].

Между прочим, писать \left( и \right) нужно только, если нужны скобки большего размера, например, если между ними дробь. Можно писать просто ( и ).

1

@light-revan

Посмотрите, вот здесь верно упрощаю?:
--- 3 и 4 скобка
--- раскрываю 1 и 2 скобки

--- далее поглощение Х 2 раза и У 1раз в 1 скобках
--- далее распред.

верно ли и возможно ли ещё упростить?

Карно из вами приведенных выше ресурсов:


Прошу всё-же помочь с последним - там упрощается, но не пойму каким образом.

0

@3D Homer

Почему не упростить ?

В следующей строчке : в первой скобке вторая и третья конъюнкции с конца должны быть .

Еще раз повторяю: упростить — это неточно сформулированная задача. Я могу упростить все выражение за счет того, что обозначу его через g(x, y, z). Если вам преподаватель скажет найти произвольное выражение только с конъюнкцией, дизъюнкцией и отрицанием (не обязательно ДНФ или КНФ) с наименьшим количеством связок, попросите его показать вам общий метод, как это делать. Если нет общего метода, то кто сказал, что здесь вообще можно что-то упростить? Обычно ДНФ упрощают до ДНФ, а КНФ до КНФ. Для этого есть понятия тупиковой и минимальной ДНФ. Нахождение этих форм — это, по крайней мере, хорошо сформулированная задача. "Упрощать" же КНФ, чтобы в результате получилось ДНФ — это что-то странное.

Добавлено через 5 минут
Здесь можно разбить и затем , а . Итого .

1

@light-revan

Мне кажется уже вас понимаю - формы СКНФ СДНФ ДНФ КНФ - лишь формы представления, если так можно выразиться; то что КНФ упрощаем до ДНФ - не имеет смысла, вроде как дошло, осознал :-) Но, возможно, здесь это используется как упражнение для ума))

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

0

@light-revan

Посмотрите, пожалуйста, с чего начать упрощение - сразу таблицу истинности строить и по ней карту Карно, или возможно упростить до ДНФ& то с чего начать упрощение? Здесь 4 переменные, не понимаю как решать.


проверял онлайн калькулятором, но он автоматом считает и не объясняет, например:
X¬Y¬ Z + ¬XY¬Z + ¬X¬Y¬W + ¬X¬Z¬W + ¬Y¬ZW
¬W¬X¬Y + ¬XY¬Z + X¬Y¬Z + ¬Y¬ZW вот как он так упростил?
¬W¬X¬Y + ¬X¬Z + ¬Y¬Z ???

0

@3D Homer

Это и так ДНФ. Карта Карно строится без таблицы истинности. Просто элементарным конъюнкциям, в которых не все переменные, соответствуют блоки из несколько клеток (k переменных => 2^{4-k} клеток).

Карты Карно хорошо работают для 4 переменных.

По сравнению с исходной формулой в первой конъюнкции лишнее отрицание перед Y.

У меня при упрощении исходной формулы получилось .

На будущее см. правило 4.4.

1