Презентация на тему Тренажёр по булевым функциям на гиперкубе

Тренажёр по булевым функциям на гиперкубе

Авторы проекта: Уруков 5371, Малютин 5392

Санкт-Петербург, 2017

Цель

Основной задачей проекта является разработка программного обеспечения (сайта) на решение логических задач. Производится работа с булевыми функциями 4-х переменных.

Задачи, возникшие при разработке

Написать генераторы для каждой задачи
Спроектировать интерактивный гиперкуб

Грубый перебор не подходит для генерации

Генерация монотонной функции

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

Генерация самодвойственной функции

Производится обход до середины. В симметрично расположенных значениях устанавливается противоположное значение.

Генерация функций с фиктивными переменными

Генерировать функцию из трёх переменных без фиктивных переменных. Значения функции ставить в соответствующие позиции таким образом, чтобы одна переменная была фиктивной.

Генерация выражения

( [t-z]
(or, and, =>, +)
[t-z]
(or, and, =>, +)
[t-z] )
(or, and, =>, +)
[t-z]
(or, and, =>, +)
[t-z]

(¬Y=>(T=>Z)) && ¬T && X

T && (X xor ¬T)=>Y xor Z 

(¬Z xor (¬Y || (Z xor ¬X))) || ¬T 

Генерация задач на минимальное ДНФ

По гиперкубу можно минимизировать ДНФ. Для этого необходимо представить каждую вершину в виде дизъюнкта. Затем посмотреть на положения единичек.

Правила:
Если на концах ребра вершины имеют значения 1, то дизъюнкция сокращается на 1 переменную, которая на этом ребре фиктивна.
Если два параллельных ребра сокращаются, то сокращается плоскость, т.е. дизъюнкт сокращается до двух переменных
Если в вершинах трехмерной грани стоят единицы, то дизъюнкты сокращаются до 1 переменной

База задач

Клиент

Генератор задач

Сервер