Консультация № 192964
20.03.2018, 04:11
0.00 руб.
1 1 1
Уважаемые эксперты! Пожалуйста, помогите с решением задач по дискретной математике:
1. Выяснить, применима ли машина Тьюринга, заданная программой P , к слову
S , и если применима, то указать результат применения машины Тьюринга к данному
слову (рисунок 1 во вложении.

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


Прикрепленные файлы:
69e5cb911b9fd9e35a9f222e75986f17bbdbd190.jpg

Обсуждение

давно
Мастер-Эксперт
17387
18345
21.03.2018, 07:34
общий
это ответ
Здравствуйте, Маргарита!

Я думаю, что второе задание можно выполнить так.

Пусть дана формула (x1 [$8744$] x2) [$8658$] ([$172$]x1 [$8744$] x2)x3. (По техническим причинам для обозначения импликации я использую двойную стрелку вместо одинарной.)

Сначала заменим импликацию дизъюнкцией. Получим [$172$](x1 [$8744$] x2) [$8744$] ([$172$]x1 [$8744$] x2)x3.

Заменим отрицание дизъюнкции конъюнкцией: ([$172$]x1[$172$]x2) [$8744$] ([$172$]x1 [$8744$] x2)x3.

Воспользуемся дистрибутивностью конъюнкции относительно дизъюнкции: ([$172$]x1[$172$]x2) [$8744$] ([$172$]x1x3 [$8744$] x2x3).

Раскроем скобки: [$172$]x1[$172$]x2 [$8744$] [$172$]x1x3 [$8744$] x2x3.
Об авторе:
Facta loquuntur.
Форма ответа