IPB
ЛогинПароль:

> Компиляция правил для данного раздела

1. Заголовок темы должен быть информативным. В противном случае тема закрывается и удаляется ...
2. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
3. Одна тема - один вопрос (задача)
4. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> СКНФ и СДНФ, Логика.
сообщение
Сообщение #1


Профи
****

Группа: Пользователи
Сообщений: 920
Пол: Женский
Реальное имя: Марина

Репутация: -  2  +


Помогите доказать следующие теоремы:
1. если формула имеет совершенную дизъюнктивную форму, то такая форма единственна.
Вот мои соображения: пусть формула фи имеет 2 различные формы: СДНФ1 и СДНФ2.
пусть некая элементарная конъюнкция СДНФ1 не содержится в сДнф2. Дальше ... не знаю....наверное задать литералам (элементарным высказываниям или их отрицаниям), вход. в эту элементарн. конъюнкцию, какие-то значения.....

???

2. Доказать, что тождественно-истинная и тождественно-ложная фомулы не имеют совершенных форм.
Мне кажется, что исходить нужно из того, что каждый литерал ( элементарное высказывание или его отрицание) входит по 1 разу в элементарн. дизъюнкцию или конъюнкцию.....

Сообщение отредактировано: 18192123 -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


1. ....
то есть существует некая эл. кон, вход в СДНФ1, но не вход. в СДНФ2 (или наоборот - не важно). Соответственно, на этом наборе переменных СДНФ1 имеет истину, СДНФ2 - ложь, то есть одна из СДНФ не на всех наборах равна исходной ф-ции -> не является ее СДНФ.

2. Здрааасте. Имеют. Только по одной, а не две, как у остальных ф-ций.


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Пионер
**

Группа: Пользователи
Сообщений: 69
Пол: Мужской

Репутация: -  3  +


Цитата
Доказать, что тождественно-истинная и тождественно-ложная фомулы не имеют совершенных форм.


Тождественно-истинная формула есть тавтология, значит верна при всех возможных наборах переменных, для нее строиться СДНФ состоящий из всех возможных наборов пропозициональных переменных и их отрицания (имеется ввиду входящих в элементарные дизъюнкты).

Соответственно, если мы отрицаем тождественно истинную формулу, то получим тождественно ложную, и тогда пользуясь равносильностью: *(AB)=*A+*B, мы перейдем к СКНФ, а ввиду того, что содержание всех возможных дизъюнктов (это для СДНФ) есть в 1 части доказательства, то получаем все возможные варианты (но уже конъюнктов).
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Профи
****

Группа: Пользователи
Сообщений: 920
Пол: Женский
Реальное имя: Марина

Репутация: -  2  +


Цитата(мисс_граффити @ 9.04.2007 19:46) *



2. Здрааасте. Имеют. Только по одной, а не две, как у остальных ф-ций.


smile.gif Ха! А нам препод сказал, что сДНФ и СКНФ они не имеют и задал доказать....
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


Одна не имеет СДНФ, другая не имеет СКНФ.
То есть каждая из них лишена только одной из совершенных форм.


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 27.09.2020 4:20
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name