Математические и логические основы...

← →
Andruh (2006-02-05 07:18) [0]

задача такова: по заданному логическому уравнению уравнению потсроить простейшу схему на элементах (И,ИЛИ,НЕ), предоставить возможность изменнения наборов (1,0) этого уравнения...
Как не сяду че-нить делать ни-че понять не могу с чего начать...
Основная проблема с решением самого логического уравнения, т.е. вводимое уравнение состоит из трех элементов (x,y,z), которое принимает только один набор значений...
Вопрос: если можно подскажите как правильно пользоваться логическими операциями...
З.Ы. не судите если это совсем глупо, но я ни че понять не могу...

← →
Andruh (2006-02-05 07:48) [1]

ошибочка!

> которое принимает только один набор значений...

которое может принимать разные значения, но уравнение не изменяется...

← →
Defunct © (2006-02-05 07:52) [2]

И-ИЛИ-НЕ - функционально полный набор, более того даже избыточен. Для реализации любого уравнения булевой логики достаточно набора И-ИЛИ.

Начните с простого. импликанты вида X1*X2*X3*...*Xn заменяйте n входовым элементом И, операцию сложения (V) - элементом ИЛИ. Инверторы ставьте для инвертирования входных сигналов, там где требуется (входной сигнал с чертой над ним).

← →
SergP © (2006-02-05 08:10) [3]

> Для реализации любого уравнения булевой логики достаточно
> набора И-ИЛИ.

Наверное имелось ввиду И-НЕ или ИЛИ-НЕ ?

← →
Defunct © (2006-02-05 08:27) [4]

SergP © (05.02.06 08:10) [3]

да именно они (и то, и то).

отвечу самому себе набор И-ИЛИ не удовлетворяет требованию к не монотонности..

← →
TUser © (2006-02-05 09:48) [5]

> Для реализации любого уравнения булевой логики достаточно
> набора И-ИЛИ.

Вообще, - достаточно только одной операции.

← →
Defunct © (2006-02-05 11:18) [6]

TUser © (05.02.06 09:48) [5]

?

← →
palva © (2006-02-05 12:15) [7]

Искать в Яндексе слова "дизъюнктивная нормальная форма"

http://ptca.narod.ru/lec/lec1.html
http://www.iteach.ru/UMPcatalog/f_v801/u_k901/f_l901?path=web%2Fdnf.htm

Или в любом хорошем учебнике по логике.

← →
Gorger © (2006-02-06 05:56) [8]

Может, кинешь мне задачку на мыло? Я попробую решить.
mailto: ugluk@netman.ru

← →
Gorger © (2006-02-06 05:58) [9]

Виноват, стормозил.

← →
TUser © (2006-02-06 06:13) [10]

> ?

Теормеа Буля. Любое логическое выражение можно выразить через И, Или, Не.
Доказывать не буду, хотя доказательство есть.

Теперь введем, например, операцию nor (т.н. функция Пирса)
a nor b == (not a) or (not b)

Легко проверить, что
not a = a nor a
a or b = (a nor a) nor (b nor b)
a and b = (a nor b) nor (a nor b)

Т.о. все можно выразить через nor. На самом деле таких функций несколько.

← →
TUser © (2006-02-06 06:16) [11]

> На самом деле таких функций несколько.

Точного доказательства не видел, но у меня есть подозрение, что любая из 16-ти возможных бинарных булевых функций достаточна для представления любой булевой функции. Буду рад комментариям людей, знакомых с математикой лучше меня.

← →
Andruh (2006-02-06 16:23) [12]

нет, всего этого мне не надо, мне нужно иммено только работать с эелементами И ИЛИ НЕ составных функций мне не надо

← →
Andruh (2006-02-06 16:31) [13]

при начале работы, появился вопрос, который меня несколько смутил
при вычислении, допустим, такого уравнения: x or not(y) or z
при определенных наборах значений получается ответ: -1
Тип boolean допускает тока два значения (1,0), как может получиться ответ отрицательный? Или может -1 принимать как 1?

← →
Defunct © (2006-02-07 02:16) [14]

> Andruh
какие типы у X Y Z?

если проинвертировать числовую переменную равную нулю, то в доп. коде получится число 1...111 воспринимаемое процессором как -1.

определите X Y и Z как boolean. тогда будет все как надо.

TUser © (06.02.06 06:13) [10]
что любая из 16-ти возможных бинарных булевых функций достаточна для представления любой булевой функции. Буду рад комментариям людей, знакомых с математикой лучше меня.

Учите матчасть. Теорема о функциональной полноте.

Для того чтобы система S булевых функций была функционально полной, необходимо и достаточно, чтобы эта система содержала хотя бы одну булеву функцию, не сохраняющую константу 1, хотя бы одну булеву функцию, не сохраняющую константу 0, хотя бы одну несамодвойственную булеву функцию, хотя бы одну нелинейную булеву функцию и хотя бы одну немонотонную булеву функцию.

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

Перечислим предполные классы булевых функций:
булевы функции, сохраняющие константу 0;
булевы функции, сохраняющие константу 1;
самодвойственные булевы функции;
линейные булевы функции;
монотонные булевы функции;

http://ptca.narod.ru/lec/lec3.html

← →
evvcom © (2006-02-07 10:24) [15]

> по заданному логическому уравнению

так уравнение задано? Или все же имеется ввиду "булево выражение"?

> предоставить возможность изменнения наборов (1,0) этого
> уравнения

что это значит? Входные данные? Ну тогда точно не уравнение, а выражение или функция.
Конкретика есть какая-нибудь? А то абстрактно не понятно, что тебе (преподу) надо. Очень похоже, что ты выложил общее для всех вариантов задание, а конкретное выражение, заданное для твоего варианта ты даже не удосужился посмотреть, не то что выложить.

← →
Andruh (2006-02-09 14:05) [16]

> определите X Y и Z как boolean. тогда будет все как надо.

у меня это описано так:
var x,y,z,rez:boolean;
а результат тотже... (-1, при определенном наборе)

> Очень похоже, что ты выложил общее для всех вариантов задание,
> а конкретное выражение, заданное для твоего варианта ты
> даже не удосужился посмотреть, не то что выложить.

я хочу что-бы программа работала с любым уравнением(выражением,функцией)(так хочу я, преподу вообще не это надо)
дальше мне предстоит делать графическую часть(именно которая волнует препода(меня она будет волновать позже, когда начну ее делать :) ))

← →
evvcom © (2006-02-09 14:43) [17]

У тебя много тараканов в голове. Ты сначала сделай то, что требует препод, потом выгони тараканов (если они еще не разбегутся к этому времени), а уж потом будешь самодеятельностью заниматься будешь.

← →
Andruh (2006-02-09 18:48) [18]

2evvcom:

> У тебя много тараканов в голове

Вы правы, безусловно, но ведь с ними(тараканами) куда интереснее делать творческую работу... ;)

А на счет графики(которую он(препод) хочет от меня получить) он сам толком не может решить как ее лучше реализовать, получается у меня есть задание уже долгое время, а процесса работы никакого, вот я и решил пока препод не выдаст мне свою прихоть, я буду заниматься самодеятельностью, глядишь и рисовать ничего не надо...

← →
Andruh (2006-02-09 19:10) [19]

прошу прощенья за оффтоп в [18]...
хотелось-бы пометить сообщение [16]

> а результат тотже... (-1, при определенном наборе)

приводите код, "будем посмотреть" ;>

> он сам толком не может решить как ее лучше реализовать

Он и не должен решать, как ее реализовывать. Это дело программиста. Он должен только сказать, что должна делать программа и может указать, что использовать (для закрепления пройденной темы), обычно это Canvas какого-нить TImage, хотя можно прямо на форме. Может дать пожелания, как это должно выглядеть, а может и не дать. Но все это он вовсе не должен. Так что ты сам время тянешь, а его обычно, ой, как не хватает.

← →
Andruh (2006-02-11 12:20) [22]

2evvcom: может вы и правы...

2All:

procedure TForm1.Button1Click(Sender: TObject); var x1,x2,x3,rez:boolean; begin x1:=strtobool(edit1.text); x2:=strtobool(edit2.text); x3:=strtobool(edit3.text); rez:=strtobool(edit1.text);//(x or not(y) or z); label5.Caption :="Ðåçóëüòàò óðàâíåíèÿ: "+booltostr(rez); end;

Andruh (11.02.06 12:20) [22]

если проблема только с выводом строки, так определите свою функцию BoolToStr например так:

function BoolToStr( value: boolean):string; begin if value then Result := "True (1)" else Result := "False (0)" end;

← →
Andruh (2006-02-11 16:43) [24]

большое спасибо Defunct!

Математические и логические основы... Найти похожие ветки