Красным цветом — вершины, относительно которых мы пока не можем сказать, принадлежат ли они данной компоненте связанности, синим — вершины, принадлежащие данной компоненте связанности и ультрафиолетовым — вершины, принадлежащие данной компоненте связанности, лежащие на границе волны.
1. Раскрасить все вершины графа в красный цвет
2. Если есть вершины красного цвета, выполнить следующий шаг, иначе закончить выполнение алгоритма.
3. Выбрать одну произвольную вершину xi красного цвета и покрасить ее в ультрафиолетовый цвет. Эта вершина, очевидно, принадлежит своей компоненте связанности, но ее окружение еще не рассмотрено.
4. Повторять следующий шаг, пока есть хоть одна вершина ультрафиолетового цвета. Если таких вершин нет, перейти к шагу 2. Все вершины, покрашенные в синий цвет на данной итерации шага 3 принадлежат одной компоненте связанности.
5. Выбрать вершину ультрафиолетового цвета и покрасить ее в синий цвет, а все красные вершины, смежные с ней, в ультрафиолетовый.
Этот алгоритм классифицирован как волновой — из случайно выбранной точки разгоняем круговую волну, помечая все точки, попавшие на волновой фронт, как одну компоненту связанности.
Определим тип данных PropStat, представляющий высказывания:
type Name = Char
data PropStat = Simple Name
| And PropStat PropStat -- p && q
| Or PropStat PropStat -- p || q
| Not PropStat -- not p
| Implies PropStat PropStat -- p -> q
| Equiv PropStat PropStat -- p <-> q (or p == q)
deriving Show
Задача: создайте модуль PropLogic.hs, который должен содержать функции описанные ниже.
1. Определите тип окружение, с помощью которого задается конкретная интерпретация переменных.
type Environment a b = [(a, b)]
Определите функцию
allEnvs :: [Name] -> [Environment Name Bool]
Функция allEnvs xs возвращает список всех возможных интерпретаций переменных из списка.
Например,
allEnvs ['a', 'b'] Þ [[('a',True),('b',True)],[('a',True),('b',False)],[('a',False),('b',True)],
[('a',False),('b',False)]]
2 . Определите функцию stat :: Int -> PropStat, которая по данному целому числу возвращает некоторое высказывание. Функция stat будет полезна для тестирования ваших функций. Определите следующее:
stat 1 = c ~ d
stat 2 = a É (a Ú b)
stat 3 = (c É d) ~ (d É c)
stat 4 = Ø (Ø a && Ø c) ~ (Ø c É a)
Заметим, что правые стороны этих уравнений написаны в привычной логической форме: они должны быть заменены на соответствующие выражения типа PropStat.
3 . Определите функцию eval :: PropStat -> Environment Name Bool -> Bool, которая берет высказывание p и интерпретацию e, и оценивает p в интерпретации e.
Например, eval (stat 3) [('c', True), ('d', False)] Þ False, и
eval (stat 3) [('c', False), ('d', False)] Þ True.
Заметим, что p É p’ ºØ p Ú p’.
4 . Определите функцию vars :: PropStat -> [Name], которая возвращает список всех переменных без дупликатов, содержащихся в высказывании. (Подсказка: Определите рекурсивную функцию allvars, возвращающую список переменных с дубликатами и воспользуйтесь функцией nub из библиотеки List.)
Например, vars (stat 3) Þ "cd".
5 . Высказывание p называется тавтологией, если p есть истина при любой интерпретации переменных. Определите функцию, проверяющую является ли высказывание тавтологией: tautology :: PropStat -> Bool
Например, tautology (stat 2) Þ True, tautology (stat 3) Þ False, и
tautology (stat 4) Þ True.
6 . Пусть равенство высказываний понимается как логическая эквивалентность. Для определения равенства для высказываний введите декларацию экземпляра в виде
instance Eq PropStat where
p == p’ = …
Например, stat 1 == stat 3, но stat 3 /= stat 4.
7 . Определите функцию showPropStat :: PropStat -> String, которая берет высказывание и возвращает строку, представляющую это высказывание. Заключайте все подвыражения в скобки.
Например, showPropStat (stat 3) Þ "((c -> d) <-> (d -> c))"
8 . Все высказывания могут быть переписаны к виду, содержащему только операции É и Ø. Справедливы следующие правила:
p & p’ º Ø (Øp Ú Ø p’)
p Ú p’ º Ø p É p’
p ~ p’ º (p É p’) & (p’ É p)
Используя эти правила рекурсивно, определите функцию
transform :: PropStat->PropStat, которая переписывает высказывание в эквивалентную (É, Ø)–форму.
Например:
showPropStat (transform (stat 2)) Þ "(a -> ((not a) -> b))"
showPropStat (transform (stat 3)) Þ
"(not ((not (not ((c -> d) -> (d -> c)))) -> (not ((d -> c) -> (c -> d)))))"
9. Напишите функцию insertNeg, которая приводит формулу к виду с тесными отрицаниями: insertNeg w выдает логическую формулу, получающуюся из логической формулы w внесением всех операторов отрицания внутрь конъюнкций и дизъюнкций.
Пример:
> insertNeg (Not (And (Var 'x') (Or (Var 'y') (Not (Var 'x')))))
Or (Not (Var 'x')) (And (Not (Var 'y')) (Var 'x')))
В логических обозначениях: Ø(x & (y Ú Øx)) => Øx Ú (Øy & x)
Алфавит языка логики предикатов содержит:
1) символы предметных переменных x, y, z и т. д.;
2) символы предикатов P, Q, R и т. д.;
3) символы логических операций & (конъюнкция), v (дизъюнкция), – (отрицание), => (импликация), <=> (эквиваленция);
4) символы кванторов A («для всех»), E («существует) .
Определение формул в нотации Бэкуса-Наура:
formula ::= term | term op term
term ::= factor | factor & factor
factor ::= predicate | quantifier | (formula) | - (formula)
variable ::= x | y | z
nameOfPredicate ::= P | Q | R
predicate ::= nameOfPredicate(variable {,variable})
op ::= v | => | <=>
nameQuantifier ::= A | E
quantifier ::= nameQuantifier variable (formula)
Напоминаем, что метасимволы{ и } используются для задания синтаксических конструкций произвольной длины. Таким образом, {объект} означает, что объект может повторяться ноль или более раз.
Примеры формул:
P(x, y, x), Q(z, z, z, z) – предикаты;
– (P(x) & Ax(P(x) => Q(x,y))) v R(x,y).
1. Введите тип Formula на Haskell’е для представления формул языка логики предикатов.
2. Напишите функцию readFormula :: String -> Formula, которая осуществляет парсинг (синтаксический разбор) логической формулы, представленной в виде строки (например, "– (P(x) & Ax(P(x) => Q(x,y))) v R(x,y)") и представляет в виде значения типа Formula.
3. Напишите функцию showFormula :: Formula -> String, которая изображает
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.
