В формуле указать свободные и связанные переменные. Привести формулу к предваренной форме. Для каждого преобразования указать, какие равносильности были использованы.

23 января 2025
Логика

Условие:

1. В формуле указать свободные и связанные переменные. Привести формулу к предваренной форме. Для каждого преобразования указать, какие равносильности были использованы. Для итоговой формулы указать свободные и связанные переменные.

2.Дана машина Тьюринга с алфавитом и программой

Определить конфигурацию, в которую переходит машина Тьюринга после выполнения не более чем 5 команд, если начальная конфигурация была

Решение:

1. В заданной формуле все переменные связанные. Приводим ее к предваренной нормальной форме.

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