---
# System prepended metadata

title: Mikołaj Fornal - Logika cyfrowa - lista 01

---

# 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>

![](https://i.imgur.com/hAhcbBN.png)

## 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>

![](https://i.imgur.com/Zn7MoJ3.png)

## 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:
![](https://i.imgur.com/wO6Sy4h.png)

## 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}$

![](https://i.imgur.com/QowecPP.png)

## 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:
![](https://i.imgur.com/rkxzPen.png)

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ć:
![](https://i.imgur.com/yaSOxZ2.png)
