Форум программистов, компьютерный форум, киберфорум
Наши страницы
Lisp
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.70/23: Рейтинг темы: голосов - 23, средняя оценка - 4.70
eddilou
3 / 3 / 0
Регистрация: 21.11.2010
Сообщений: 194
1

Распознание логические формулы в конъюнктивной нормальной форме

21.10.2012, 18:10. Просмотров 4705. Ответов 50
Метки нет (Все метки)

Всем привет, помогите пож-та, не очень силен в Lisp но очень нужно, стоит интерпретатор XLISP, пишется под чистым лиспом т.е. Common Lisp, здание заключ в следующем:
Булева формула есть терм, определяемый следующим образом: константы true и false -булевы формулы; если X и Y - булевы формулы, то и списки (X v Y), (X & Y), (~ X) -булевы формулы, здесь v и & - бинарные инфиксные операторы дизъюнкции и конъюнкции, а ~ - унарный оператор отрицания. Напишите функцию, распознающую логические формулы в конъюнктивной нормальной форме, т.е. формулы, являющиеся конъюнкцией дизъюнкций литералов, где литерал - атомарная формула или ее отрицание.
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.10.2012, 18:10
Ответы с готовыми решениями:

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

Составьте программу нахождения совершенной конъюнктивной нормальной формы
Составьте программу нахождения совершенной конъюнктивной нормальной формы (с.к.н.ф.) на любом...

Привести формулы к предваренной нормальной форме. Не уверена в правильности решения(+)
1. \overline{\forall xP(x)}\vee \exist x Q(x,y)= \exist x\overline{P(x)}\vee\exist xQ(x,y)= \exist...

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

Приведите к предваренной нормальной форме следующие формулы логики предикатов
Приведите к предваренной нормальной форме следующие формулы логики предикатов.

50
Catstail
Модератор
24932 / 12652 / 2317
Регистрация: 12.02.2012
Сообщений: 20,610
21.10.2012, 20:41 2
Цитата Сообщение от eddilou Посмотреть сообщение
Напишите функцию, распознающую логические формулы
- имеется в виду, что если на вход функции подана корректная формула, то функция должна вернуть T, иначе Nil?

Добавлено через 51 минуту
Вспомогательная функция - является ли ее аргумент переменной:

Lisp
1
(defun chk-var (x) (And (atom x) (NOT (NULL x)) (NEQ x '&) (NEQ x 'v) (NEQ x '~) (Not (numberp x))))
И решение задачи:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
(defun check-form (x)
   (cond ((EQ x 'true)  t)
         ((EQ x 'false) t)
         ((chk-var x) t)
         ((listp x) 
               (cond ((AND (EQ '~ (car x)) (chk-var (cadr x))) t)
                     ((AND (EQ '~ (car x)) (check-form (cadr x))) t)
                     ((AND (chk-var (car x)) (member (cadr x) '(v &)) (chk-var (caddr x))) t)
                     (t (AND (check-form (car x)) (member (cadr x) '(v &)) (check-form (caddr x))))))
         (t nil)))
 
;; проверка:
 
(check-form '(~ (a & (~ (a v true)))))
 
==> T
 
(check-form '(a ~ b))
 
==> NIL
Вообще надо потщательнее потестировать. Вероятно, можно написать рациональнее.
0
eddilou
3 / 3 / 0
Регистрация: 21.11.2010
Сообщений: 194
21.10.2012, 22:27  [ТС] 3
не работает, дабы ругается на неизвестную функцию NEQ, может она как то иначе называется или что то иное просто знаю eq и тд но NEQ в книге не нашел вообще и не очень понятно что за cadr и caddr и в чем отличие их? просто не ах в лиспе вот и спрашиваю дабы в книге тоже нет таких функций
0
Catstail
Модератор
24932 / 12652 / 2317
Регистрация: 12.02.2012
Сообщений: 20,610
22.10.2012, 10:16 4
Попробуй так:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
(defun chk-var (x) (And (atom x) (NOT (NULL x)) (NOT(EQ x '&)) (NOT (EQ x 'v)) (NOT (EQ x '~)) (Not (numberp x))))
 
==> chk-var
 
(defun check-form (x)
   (cond ((EQ x 'true)  t)
         ((EQ x 'false) t)
         ((chk-var x) t)
         ((listp x) 
               (cond ((AND (EQ '~ (car x)) (chk-var (cadr x))) t)
                     ((AND (EQ '~ (car x)) (check-form (cadr x))) t)
                     ((AND (chk-var (car x)) (member (cadr x) '(v &)) (chk-var (caddr x))) t)
                     (t (AND (check-form (car x)) (member (cadr x) '(v &)) (check-form (caddr x))))))
         (t nil)))
 
==> check-form
 
(check-form '(~ (a & (~ (a v true)))))
 
==> T
 
(check-form '(a ~ b))
 
==> NIL
 
(check-form '(a & b))
 
==> T
NEQ в HomeLisp = (NOT (EQ ..)) а насчёт CADR и CDDR не волнуйся - они есть во всех Лиспах:
CADR = (CAR (CDR ...)); CADDR = (CAR (CDR (CDR ...)))

А в каком Лиспе ты это делаешь?
1
22.10.2012, 10:16
eddilou
3 / 3 / 0
Регистрация: 21.11.2010
Сообщений: 194
22.10.2012, 16:57  [ТС] 5
Делаю в XLISP и используется чисто Common Lisp без всяких новоротов и дополн функц и тп так нам сказали делать

Добавлено через 9 минут
теперь работает, но вот что интересно, а как различать какая форма является КНФ а какая нет, чтоб скажем так продемонстрировать преподавателю? и почему используется в true и false??
0
Catstail
Модератор
24932 / 12652 / 2317
Регистрация: 12.02.2012
Сообщений: 20,610
22.10.2012, 17:48 6
Введи некорректное выражение, например (a b c) - не есть КНФ, а вот (a & b) - является таковой
0
eddilou
3 / 3 / 0
Регистрация: 21.11.2010
Сообщений: 194
22.10.2012, 18:07  [ТС] 7
спасибо за пояснение!! большое спасибо!!) теперь осталось понять как работает вспомогательная функция, она идет по списку т.е. сравнивает является ли атом и не нулевой затем след сранение что оно делает и что она возвращет или как она предупреждает что типа нет такого то символа и тд?
0
Catstail
Модератор
24932 / 12652 / 2317
Регистрация: 12.02.2012
Сообщений: 20,610
24.10.2012, 11:11 8
Цитата Сообщение от eddilou Посмотреть сообщение
как она предупреждает что типа нет такого то символа и тд?
- никак. Просто возвращает Nil, что значит "Представленный список не есть КНФ"
0
eddilou
3 / 3 / 0
Регистрация: 21.11.2010
Сообщений: 194
30.10.2012, 16:00  [ТС] 9
Цитата Сообщение от Catstail Посмотреть сообщение
- никак. Просто возвращает Nil, что значит "Представленный список не есть КНФ"
программа не работает дабы перед скобкой не должно быть отрицание, и при введении кнф он нил возвращает странно как то, вот пример и определение
КНФ (Конъюнктивная Нормальная Форма) — нормальная форма, в которой булева функция имеет вид конъюнкции нескольких простых дизъюнктов.
Пример КНФ: (x v y) & (y v ~z)
0
Catstail
Модератор
24932 / 12652 / 2317
Регистрация: 12.02.2012
Сообщений: 20,610
30.10.2012, 20:11 10
Я писал функцию по заданию, которое было приведено в самом начале. Оно основано на том, что отрицание заключается в скобки.
0
eddilou
3 / 3 / 0
Регистрация: 21.11.2010
Сообщений: 194
30.10.2012, 23:43  [ТС] 11
ну вот такой странный препод он сказал мол не верно фурычит я аж расстроился

Добавлено через 1 час 29 минут
Цитата Сообщение от Catstail Посмотреть сообщение
Я писал функцию по заданию, которое было приведено в самом начале. Оно основано на том, что отрицание заключается в скобки.
я все понимаю, но проблема в том что если например ~(x v b) и что то еще написать то он выдает что якобы верно
0
Catstail
Модератор
24932 / 12652 / 2317
Регистрация: 12.02.2012
Сообщений: 20,610
31.10.2012, 11:25 12
Цитата Сообщение от eddilou Посмотреть сообщение
я все понимаю, но проблема в том что
- а, это другое дело... Буду разбираться.
0
eddilou
3 / 3 / 0
Регистрация: 21.11.2010
Сообщений: 194
01.11.2012, 22:53  [ТС] 13
Цитата Сообщение от Catstail Посмотреть сообщение
- а, это другое дело... Буду разбираться.
в чем могла бы быть ошибка? может как то организовать проверку такую что перед скобкой не должно быть отрицания типа

Lisp
1
((AND (EQ '~ (car x)) (EQ '( (cadr x))) NIL)
может как то так или иначе что ли...
0
eddilou
3 / 3 / 0
Регистрация: 21.11.2010
Сообщений: 194
03.11.2012, 15:49  [ТС] 14
не подскажешь? как сделать? или что добавить для проверки
0
Catstail
Модератор
24932 / 12652 / 2317
Регистрация: 12.02.2012
Сообщений: 20,610
03.11.2012, 19:53 15
Да, понял, что я сделал не так... Моя программа просто анализирует произвольные логические выражения на корректность. Для распознавания именно КНФ нужна несколько другая программа.
0
eddilou
3 / 3 / 0
Регистрация: 21.11.2010
Сообщений: 194
03.11.2012, 22:24  [ТС] 16
Цитата Сообщение от Catstail Посмотреть сообщение
Да, понял, что я сделал не так... Моя программа просто анализирует произвольные логические выражения на корректность. Для распознавания именно КНФ нужна несколько другая программа.
и как теперь быть? что нужно изменить чтоб программа работала как надо?
0
Catstail
Модератор
24932 / 12652 / 2317
Регистрация: 12.02.2012
Сообщений: 20,610
04.11.2012, 13:49 17
Завтра сделаю

Добавлено через 14 часов 29 минут
Вот что получилось:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
;; проверка переменной
 
(defun chk-var (x) (cond ((atom x) 
                          (AND (NOT (NULL x)) (NEQ x '&) (NEQ x 'v) (NEQ x '~) (Not (numberp x))))
                         (t (AND (= (length x) 2)
                                 (EQ  '~ (car x))
                                 (NEQ '& (cadr x))
                                 (NEQ 'V (cadr x))
                                 (NOT (numberp x))))))
 
;; проверка элементарной дизъюнкции
 
(defun chk-diz (x) (cond ((AND (= 3 (length x)) (chk-var (car x)) (chk-var (caddr x)) (EQ 'v (cadr x))) t)
                         (t nil)))
 
;; собственно проверка КНФ:
 
(defun chk-kon (x) 
    (cond ((null x) t)
          ((chk-diz x) t)
          ((= 1 (length x)) (chk-kon (car x))) 
          ((= 3 (length x)) (AND (chk-diz (car x)) (chk-diz (caddr x)) (EQ '& (cadr x))))
          (t (AND (chk-kon (subseq x 0 3)) (EQ '& (car (subseq x 3 1))) (chk-kon (subseq x 4))))))
                         
;; тесты:
 
(chk-kon '((a v b) & (c v d) & (False v (~ w)) ))
 
==> t
 
(chk-kon '((a v b) & (c v d) & (q v (~ w)) ))
 
==> t
 
(chk-kon '((a v b) v (c v d) & (False v (~ w)) ))
 
==> nil
0
eddilou
3 / 3 / 0
Регистрация: 21.11.2010
Сообщений: 194
04.11.2012, 16:13  [ТС] 18
Цитата Сообщение от Catstail Посмотреть сообщение
Вот что получилось:
немного не понятно, не могли бы пож-та пояснить, для чего служат цифры? что делает subseq?
0
Catstail
Модератор
24932 / 12652 / 2317
Регистрация: 12.02.2012
Сообщений: 20,610
04.11.2012, 16:42 19
subseq - это функция Лиспа (Common; и в HomeLisp-е тоже есть). Она имеет два обязательных параметра и один необязательный. Первый параметр - список. Второй параметр - начальный элемент (нумерация с нуля) , третий - длина. Функция возвращает отрезок списка с позиции, заданной вторым параметром и длиной, заданной третьим. Если длина опущена - возвращается список до конца.

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
(defun chk-kon (x) 
    (cond ((null x) t)  ;; пустая КНФ
          ((chk-diz x) t) ;; отдельно стоящая дизъюнкция
          ((= 1 (length x)) (chk-kon (car x)))  ;; КНФ в скобках
          ;; Если длина =3, то первый терм должен быть дизъюнкцией;
          ;; Второй - символом &;
          ;; третий терм должен быть дизъюнкцией;
          ((= 3 (length x)) (AND (chk-diz (car x)) (chk-diz (caddr x)) (EQ '& (cadr x))))
          ;; отрезаем первые 3 терма и проверяем на КНФ
          ;; следующий символ - &
          ;; хвост - тоже проверяем на КНФ
          (t (AND (chk-kon (subseq x 0 3)) (EQ '& (car (subseq x 3 1))) (chk-kon (subseq x 4))))))
1
eddilou
3 / 3 / 0
Регистрация: 21.11.2010
Сообщений: 194
06.11.2012, 15:03  [ТС] 20
[QUOTE=Catstail;3651207]/QUOTE]
странно ввожу те же примеры он мне странную ошибку выдает
sequence out of bound - 1
не оч понимаю что за ошибка и почему она выскакивает когда ввожу например то же самое что и вы
(chk-kon '((a v b) & (c v d) & (q v (~ w)) ))
если ввожу
(chk-kon '((a v b) & (c v d)))
то норм все, так понял ошибка какая то связанная с проверкой длиной или что то еще... как исправить?
0
06.11.2012, 15:03
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.11.2012, 15:03

Привести к предваренной нормальной форме (ПНФ) и к сколемовской нормальной форме (СНФ)
Привести к предваренной нормальной форме (ПНФ) и к сколемовской нормальной форме (СНФ). \ \forall...

Логические формулы
Подскажите, как в столбце Размер штрафа при помощи функции из категории Логические рассчитать...

Логические формулы
Как записать логическими формулами следующие высказывание: Если медиана треугольника, проведенная...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.