# Fundamentos de Lógica

## Lógica Proposicional

É a matemática de $2$ (dois) valores Booleanos, `VERDADEIRO` (`TRUE`, `T`, `1`) e `FALSO` (`FALSE`, `F`, `0`), 
e $5$ (cinco) operadores.

### Operadores da Lógica Proposicional

|   | operador   | nome         | programação |
|---|:----------:|:------------:|:-----------:|
| 1 | $\land$    | conjunção    | `AND`, `&&` |
| 2 | $\lor$     | disjunção    | `OR`, `\|\|`  |
| 3 | $\lnot$    | negação      | `NOT`, `!`  |
| 4 | $\implies$ | implicação   |             |
| 5 | $\equiv$   | equivalência |  `==`       |

**Lógica Proposicional: Exemplos**

1. $x \land y$ é `VERDADEIRO` se $x$ e $y$ forem `VERDADEIRO`;
2. $x \lor y$ é `VERDADEIRO` se $x$ ou $y$ forem `VERDADEIRO` (ou ambos);
3. $\lnot x$ é `VERDADEIRO` se $x$ for `FALSO`;
4. $x \implies y$ é `VERDADEIRO` se $x$ for `FALSO` e $y$ for `VERDADEIRO` (ou ambos);
5. $x\equiv y$ é `VERDADEIRO` se $x$ e $y$ forem `VERDADEIRO` ou ambos forem `FALSO`.

**Lógica Proposicional: Tabela-Verdade**


  $x$   |  $y$  |    |    | $\land$ | $\lor$  | 
 ------ | ----- | -- | -- | ------- | ------  | 
 *`F`*  |  *`F`*  |    |    | `F`     |  `F`    |  
 *`F`*  |  *`T`*  |    |    | `F`     |  `T`    |  
 *`T`*  |  *`F`*  |    |    | `F`     |  `T`    |  
 *`T`*  |  *`T`*  |    |    | `T`     |  `T`    | 

|  $x$   |  $y$  |    |    | $\Rightarrow$   | $\equiv$ |
| ------ | ----- | -- | -- | ------------ | -------- |
| *`F`*  |  *`F`*  |    |    |  `T`         |    `T`   |
| *`F`*  |  *`T`*  |    |    |  `T`         |    `F`   |
| *`T`*  |  *`F`*  |    |    |  `F`         |    `F`   |
| *`T`*  |  *`T`*  |    |    |  `T`         |    `T`   |

$x$   | $\lnot x$
:---: | :---:
`F`   |  `T`      
`T`   |  `F`     

**Python3**


```python
from sympy import *
x = True
y = True
x and y
```




    True




```python
x or y
```




    True




```python
not x
```




    False




```python
Implies(x, y)
```




$\displaystyle \text{True}$




```python
x == y
```




    True



## Lógica de Predicados (lógica de primeira ordem)

A Lógica de Predicados estende a Lógica Proposicional com a adição de operadores
que trabalham com conjuntos de elementos.

**Operadores**

| operador |  operação |
|:--:|:--:|
| $\forall$ | quantificação universal (para todo) |
| $\exists$ | quantificação existencial (existe) |

**Exemplos**

$(\forall\ x \in R : S)$  - para todo $x$ em $R$, a fórmula $S$ é `VERDADEIRA`;

$(\exists \ x \in R : S)$ - existe $x$ em R, em que a fórmula $S$ é `VERDADEIRA`.


$\forall\ x \in \{2, 3, 4, 5\} : x > 1$

$\exists\ x \in \{2, 3, 4, 5\} : x > 2$


$\forall\ x \in N : x\ mod\ 2 = 0$ (é par?) `F`

$\exists\ x \in N : x\ mod\ 2 = 0$ (é par?) `V`

$\exists\ x \in N : \sqrt{x} = 2$ (é par?) `V`

## Exercícios

1. Resolva as expressões a seguir para $(x,y)=(T,T)$, $(x,y)=(T,F)$, $(x,y)=(F,T)$ e $(x,y)=(F,F)$:

- As expressões são sempre avaliadas da esquerda para a direita com exceção da existência de parênteses, por exemplo para $x \lor (x \land y)$, primeiro avalia-se $(x \land y)$ e depois a disjunção $\lor$;
- $(x,y)=(T,F)$ significa que $x=T$ e $y=F$;
- Se preferir, monte uma tabela-verdade para cada expressão.

a. $x\land y \lor x$

b. $\neg (x\lor y \land x)$

c. $x \land y \implies \neg x$

d. $(x \implies y) \equiv (x \lor y)$

e. $(x \land y) \equiv (x \lor y)$

f. $(\neg x \land y) \equiv (x \lor \neg y)$

g. $\neg(x \implies y) \equiv (x \land y)$

h. $x \lor (x \lor y) \land \neg(x \land \neg y)$

2. Para o conjunto dos números inteiros $Z$ ($\ldots, -3, -2, -1, 0, 1, 2, 3, \ldots$). Avalie as 
 seguintes expressões:
 
a. $\forall x \in Z : x \text{ é par} \land\ x \text{ é impar}$

b. $\exists x \in Z : x \text{ é par} \land\ x  \text{ é impar}$

c. $\forall x \in Z : x \text{ é par} \lor\ x \text{ é impar}$

d. $\exists x \in Z : x \text{ é par} \lor\ x \text{ é impar}$

e. $\forall x \in Z : x \text{ é primo}$

f. $\exists x \in Z : x \text{ é primo}$

g. $\neg(\forall x \in Z : x \text{ é primo} )$

h. $\forall x \in \{2,4,6,8\}, \forall y \in \{1,3,5,7\} : x + y = 11$

i. $\exists x \in \{2,4,6,8\}, \forall y \in \{1,3,5,7\} : x + y = 11$

j. $\exists x \in \{2,4,6,8\}, \exists y \in \{1,3,5,7\} : x + y = 11$

l. $\forall x \in \{0\}, \forall y \in \{1,3,5,7\} : xy = 0$

3. [Scheinerman] Assinale como verdadeira (T) ou false (F) cada uma das expressões sobre inteiros a seguir:

a. $\forall x, \forall y : x + y = 0$

b. $\forall x, \exists y : x + y = 0$

c. $\exists x, \forall y : x + y = 0$

d. $\exists x, \exists y : x + y = 0$

e. $\forall x, \forall y : xy = 0$

f. $\forall x, \exists y : xy = 0$

g. $\exists x, \forall y : xy = 0$

h. $\exists x, \exists y : xy = 0$

1817df85cfbbf9f00a726ae51df618c58115cd15
ipynb
Jupyter Notebook
notebooks/MD-Semana03.ipynb
prof-holanda/matematica-discreta
83e3a1b008baf11a11cddc5148f85c523531bf16
CC0-1.0
notebooks/MD-Semana03.ipynb
prof-holanda/matematica-discreta
83e3a1b008baf11a11cddc5148f85c523531bf16
CC0-1.0
notebooks/MD-Semana03.ipynb
prof-holanda/matematica-discreta
83e3a1b008baf11a11cddc5148f85c523531bf16
CC0-1.0
2021-05-18T13:25:27.000Z
2021-05-18T13:25:27.000Z
Qwen/Qwen-72B
1. YES
2. YES