Булевая алгебра - доказательство закона Деморгана

Question

Я посмотрел на Google за булевой алгеброй (не установлено теорией) доказательство закона ДеМоргана и не смог найти его. Недостаток стека также отсутствовал в вопросах Закона ДеМоргана.

В рамках домашнего задания для моего класса СНГ 251, мы попросили, чтобы доказать часть закона де Моргана, учитывая следующие выражения:

[z + z' = 1 и zz' = 0]

доказать (xy)' = x' + y', показав, что (упрощение)

(x y) + (x' + y') = 1 и (x y)(x' + y') = 0

Моей попытки (с другом) в первом выражении было (шаги пронумерованные для справки):

1. (x y) + (x' + y')    = 1 
2. (xy + x’)(xy + y’)    = (Distributive Prop) 
3. (x + x’)(y + x’)(x + y’)(y + y’) = (Distributive Prop) // This is probably not correct 
4. (1)(y + x’)(x + y’)(1)   = (Compliment Prop) 
5. (y + x’)(x + y’)     = (0 & 1 Identity Prop) 
6. (x + x’)(y + y’)     = (Commutative Prop) // I know for a fact this is not how the commutative property works 
7. (1)(1)       = (Compliment Prop) 
8. 1        = (0 & 1 Identity Prop) 

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

Может ли кто-нибудь показать мне, где мы поступили не так, или что мы пропустили? Мы не потрудились со вторым, потому что мы знали, что первый ошибался, и что второй будет очень похожим.

PS - Я знаю, что это можно доказать с использованием таблиц истинности - и по понятным причинам, применимым в реальном мире. Однако я хотел бы понять вывод, который позволяет использовать упрощенные выражения.

Answer 1

Я не знаю, как это сделать. Это то, что я сделал:

(x.y)' = x' + y' 

& leftrightarrow;

(x.y)' + x.y = x' + y' + x.y ............ (assuming x.y != 1) 

& leftrightarrow;

1 = x' + y' + x.y 

& leftrightarrow;

1 = x' + (y' + x).(y' + y)............... (Distributive property) 

& leftrightarrow;

1 = x' + (y' + x) 

& leftrightarrow;

1 = 1 

Теперь, на первом этапе мы предположили, что x.y! = 1. Если бы это было так, то утверждение очевидно.

P.S .: Я сам не полностью удовлетворен этим доказательством, поскольку мы по-прежнему рассматриваем его в случаях. Это не однодушно!

Answer 2

Попытка сделать то, что сейчас? доказать, что 2 + 2 = 4 без учета?

«Истина и истина не соответствуют действительности, а не истине».

⊤ ∧ ⊤ & leftrightarrow; ¬ (¬ ⊤ ∨ ¬ ⊤)

"ложь и ложь не является, не ложным или не ложным."

& bottom; ∧ & bottom; & Leftrightarrow; ¬ (¬ & снизу; ∨ ¬ & снизу;)

«истинная и ложная нет, не соответствует действительности или, не ложно».

⊤ ∧ & bottom; & Leftrightarrow; ¬ (¬ ⊤ ∨ ¬ & снизу;)

«Истина заключается в том, что: истинно и верно, то нет, не так, или, не соответствует действительности и, ложь и ложные не является, не ложным или не ложным и; истинным и ложным это не правда, а не ложно ». Моя пунктуация, вероятно, немного виновата в этом, но приведенная ниже формула проверяет.

⊤ & leftrightarrow; (⊤ ∧ ⊤ & leftrightarrow; ¬ (¬ ⊤ ∨ ¬ ⊤)) ∧ (& снизу; ∧ & дна; & leftrightarrow; ¬ (¬ & снизу; ∨ ¬ & снизу;)) ∧ (⊤ ∧ & снизу; & leftrightarrow; ¬ (¬ ⊤ ∨ ¬ & снизу ;))

Answer 3

1. (X Y) + (X '+ Y') = 1;
2. (X + X '+ Y) (Y + X' + Y ') = 1; РАСПРЕДЕЛЕНИЕ AB + C = (A + C) (B + C);
3. (1 + Y) (1 + X ') = 1; SINCE Z + Z '= 1;
4. (1) (1) = 1; SINCE 1 + Z = 1;
5. 1 = 1; IDENTITY; QED

Answer 4

i bet this is a good method 
we got to prove, 
xy + x' + y' =1 
take LHS 
x'+xy+y' 
add xx' and x'y to it (notice that it does not change anything prove using simple boolean laws) 

so now 
LHS becomes, 
x'+xx'+xy+x'y+y' 
=> x'(1+x)+y(x+x')+y' 
=> x'+y+y' 
=> x'+1 
=> 1 

hence xy+x'+y'=1 
similarly do it for the other one 

Answer 5

"(x.y)' + x.y = x' + y' + x.y)"

пусть x.y=A

затем посмотреть на следующее заявление

A+A'=1