Задачка про программиста Карла

[arseniiv]

Все же знают, что с помощью nand или nor можно реализовать все булевы функции.

-- Пт июн 10, 2011 01:20:56 --

\begin{gather*} \neg a = a \mid a \\ a \wedge b = \neg (a \mid b) \\ a \vee b = \neg (\neg a \wedge \neg b) \\ 0 = a \wedge \neg a \\ 1 = \neg 0 \end{gather*}

[e2e4]

arseniiv, знать-то знают, однако речь сейчас не об этом. Задача в том, чтобы реализовать булевы функции именно на процессоре Карла, а это не одно и то же, что реализовать булевы функции, используя логические вентили.

Да, я не написал это явно, но подразумевается, что регистров всего 2 - R1 и R2.

[arseniiv]

Ясно.

[Lunatik]

Буду по мере появляения мыслей записывать (проверяйте правильность)
1) nand(a,b)
nand(b,a) - следствие (в регистре b "из b следует a")

2) nand(b,a)
nand(a,b) - следствие (в регистре a "из a следует b")

[e2e4]

Lunatik,
nand A, B; nand B, A -> A = !(A & B), B = A | !B

[Lunatik]

Я не знаю, что такое

e2e4 в сообщении #456425 писал(а):

!(A & B)

И скажите почему?

[e2e4]

Я ошибся. Исправил выше.

! - НЕ
| - ИЛИ
& - И
^ - исключающее ИЛИ
0 - ЛОЖЬ
1 - ИСТИНА

Синтаксис языков программирования. Предлагаю записывать или в таком виде, или в любом другом, но не словами "импликация, следствие" и т.п. - это очень длинно и не очевидно (для меня во всяком случае).

[Lunatik]

Насколько я знаю программирование, "$B \Rightarrow A$" и "$A \vee \overline{B}$" равносильны.

[e2e4]

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

A B Рез.
--------
0 0 1
0 1 0
1 0 1
1 1 1

то это она.

[Lunatik]

Мне обозначения очень лениво делать в теге... кстати, что самое интересное... тут по-моему кроме $A, B, A \Rightarrow B, B \Rightarrow A$ ничего сделать не удастся...

[e2e4]

Lunatik в сообщении #456434 писал(а):

кстати, что самое интересное... тут по-моему кроме $A, B, A \Rightarrow B, B \Rightarrow A$ ничего сделать не удастся...

Ну например:
nand A, A -> !A
nand A, B; nand B, B; nand A, B; nand B, B -> A = B, B = B (т.е. копирование B в A)

[Lunatik]

e2e4 в сообщении #456436 писал(а):

Ну например:
nand A, A -> !A
nand A, B; nand B, B; nand A, B; nand B, B -> A = B, B = B (т.е. копирование B в A)

А, и с самим собой можно?.. тогда буду ещё думать

[e2e4]

Цитата:

А, и с самим собой можно?

Да, конечно, в условии же было "R1 и R2 могут совпадать".

[Lunatik]

e2e4 в сообщении #456447 писал(а):

R1 и R2 могут совпадать

Я думал, что наборы в R1 и R2 могут совпадать...

-- Пт июн 10, 2011 12:39:09 --

Давайте с точностью до перестановки я писать не буду (одно и то же ж ведь)
nand A, A
nand B, B
nand A, B - A or B

-- Пт июн 10, 2011 12:47:15 --

A nor B - то же самое, только ещё nand A, A

-- Пт июн 10, 2011 12:58:13 --

nand A, A
nand B, B
nand A, B
nand B, A
nand A, A
nand B, B
nand A, B - TRUE
nand A, A - FALSE
...
Ладно, честно мне уже надоело, всё равно, если захочу доказать, что все операторы можно ими запрограммировать, придётся давать контрпример, а это долго... да и тем более я тут один...

[e2e4]

TRUE можно достигнуть за 4 шага, FALSE за 5.

Не все функции достижимы, и есть простое логическое доказательство этого факта.