# Mikołaj Fornal - Logika cyfrowa - lista 01

## Zadanie 1
> Udowodnij używając tabeli logicznej, ze $x ∨ y ∧ z = (x ∨ y) ∧ (x ∨ z)$.

| x | y | z | $y∧z$ | $x∨y∧z$ | $x∨y$ | $x∨z$ | $(x∨y)∧(x∨z)$ |
|:---:|:---:|:---:|:-----:|:-------:|:-----:|:-----:|:-------------:|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |

W kolumanch $x∨y∧z$ oraz $(x∨y)∧(x∨z)$ jest taki sam układ 0 i 1, więc formuły te są równoważne.

## Zadanie 2
> Udowodnij używając diagramu Venna, że $x∧y∨y∧z∨¬x∧z=x∧y∨¬x∧z$.

Lewa strona: <span style="color:red">$x∧y$</span>, <span style="color:green">$y∧z$</span>, <span style="color:blue">$¬x∧z$</span>
Prawa strona: <span style="color:red">$x∧y$</span>, <span style="color:blue">$¬x∧z$</span>


## Zadanie 3
>Udowodnij używając diagramu Venna, że $(x∨y∨z)∧(x∨y∨¬z) = x∨y$.

Lewa strona: <span style="color:red">$x∨y∨z$</span>, <span style="color:green">$x∨y∨¬z$</span>, <span style="color:orange">$(x∨y∨z)∧(x∨y∨¬z)$</span>
Prawa strona: <span style="color:red">$x∨y$</span>


## Zadanie 4
> Udowodnij przez przekształcenia algebraiczne algebry Boole’a, że $(x ∧ y) ∨ (x ∧ ¬y) = x$

$(x ∧ y) ∨ (x ∧ ¬y) =$ (Rozdzielność)
$x ∧ (y ∨ ¬y) =$ (Dopełnienie)
$x ∧ 1 =$ (Element neutralny)
$x$

#### Lemat pomocniczy 1: $a + ab = a$ (do zadania 5 i 6)

$a + ab =$ (Element neutralny i dopełnienie)
$a(b + \overline{b}) + ab =$ (Rozdzielność)
$ab + a\overline{b} + ab =$ (Idempotentność)
$ab + a\overline{b} =$ (Rozdzielność)
$a(b + \overline{b}) =$ (Element neutralny i dopełnienie)
$a$

## Zadanie 5
> Udowodnij przez przekształcenia algebraiczne algebry Boole’a, że $x ∧ y ∨ y ∧ z ∨ ¬x ∧ z = x ∧ y ∨ ¬x ∧ z$.

$xy + yz + \overline{x}z =$ (Element neutralny i dopełnienie)
$xy + (x + \overline{x})yz + \overline{x}z =$ (Rozdzielność)
$xy + xyz + \overline{x}yz + \overline{x}z =$ (Rozdzielność)
$x(y + yz) + \overline{x}(yz + z) =$ (Lemat pomocniczy 1)
$xy + \overline{x}z$

## Zadanie 6
> Uprość przez przekształcenia algebraiczne algebry Boole’a formułę $¬x ∧ ¬y ∨ ¬x ∧ y ∧ ¬z ∨ ¬(x ∨ ¬z)$.

$\overline{x}\overline{y} + \overline{x}yz + \overline{x+\overline{z}} =$ (Prawo de Morgana i podwójna negacja)
$\overline{x}\overline{y} + \overline{x}yz + \overline{x}z =$ (Rozdzielność)
$\overline{x}(\overline{y} + yz + z) =$ (Lemat pomocniczy 1)
$\overline{x}(\overline{y} + z)$

## Zadanie 7
> Napisz możliwie prostą formułę algebry Boole’a odpowiadającą poniższej tabelce oraz narysuj możliwie prosty układ logiczny realizujący tę formułę:

| $x$ | $y$ | $z$ | $f(x, y, z)$ |
|:---:|:---:|:---:|:------------:|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 |

Formuła: $(x + y + z)\overline{(xyz)}$
Układ:

## Zadanie 8
> Uprość poniższy układ logiczny używając praw de Morgana. Zapisz formułę algebry Boole’a odpowiadającą uproszczonemu układowi.

$\overline{\overline{(\overline{ab})(\overline{cd})}e} =$ (Prawo de Morgana i podwójna negacja)
$(\overline{ab})(\overline{cd}) + \overline{e} =$ (Prawo de Morgana)
$(\overline{a} + \overline{b})(\overline{c}+\overline{d}) + \overline{e} =$ (Rozdzielność)
$\overline{a}\cdot\overline{c} + \overline{a}\cdot\overline{d} + \overline{b}\cdot\overline{c} + \overline{b}\cdot\overline{d} + \overline{e} =$ (Prawo de Morgana)
$\overline{a+c}+\overline{a+d}+\overline{b+c}+\overline{b+d}+\overline{e}$


## Zadanie 9
> Narysuj układ logiczny, który zawiera cykl, ale pomimo tego reprezentuje pewną funkcję logiczną. Narysuj układ bez cyklu reprezentujący tę samą funkcję.

Układ z cyklem:

Gdy na wejściu jest $0$ i $0$, to bramka AND daje na wyjściu $0$, wówczas bramka OR ma na wejściu same $0$ i też daje na wyjściu $0$. Stąd XOR daje $0$.
Gdy na wejściu jest $1$ i $0$, to bramka AND daje na wyjściu $0$, zaś OR daje na wyjściu $1$. XOR ma wartość $1$.
Gdy na wejściu jest $1$ i $1$, to OR daje $1$, wówczas AND ma na wejściu same $1$ i też daje $1$. Wtedy XOR ma wartość $0$.

| a | b | AND | OR | XOR |
|:---:|:---:|:---:|:---:|:---:|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 |

Układ ten zachowuje się tak samo jak bramka XOR, można więć go uprościć: