Algebra A

Trabalho escrito - Álgebra A
Semântica de linguagens de programação

Nomes: Wilson Carlos Souza Cordeiro e Gustavo Penha.

Preliminares:
Base de Conhecimento
!= - Simbolo para diferente.
> - Simbolo para maior. n x 2 operadores, então qualquer ocorrência de expressões Booleanos vai estar precedida de IF. As únicas possibilidades são:

P = if B1 then S1. Onde S1 é outra expressão do tipo if B2 then S2. Logo as expressões B1 e B2 são precedidas de IF independente de S2. S2 pode ser uma expressao unitaria ou dupla em relaçao aos contrutores caso seja unitaria a hipotese acima fica provada por vacuidade e caso seja dupla é provado pela própria hipotese usando recursão saindo do mais interno que deve ser uma expressao unitaria em relação aos contrutores ate chegar a mais externa. P = S1;S2. Com S1 e S2 sendo:
1. S1: if B1 then S4 ; S2: skip
2. S1: if B1 then S4 ; S2: atribuiçao
3. S1: if B1 then S4 ; S2: if B2 then S3

Nos casos 1 e 2 a hipotese é provada no caso base em junçao com o primeiro caso da Hipotese Indutiva , pois mostra que toda Expressao Booleana é precedida de IF independente de qual expressao for S4 e S2 é provada por vacuidade em ambos os casos.
No caso 3 a hipotese usa o primeiro caso tratado na Hipotese Indutiva, pois mostra que independente de qual expressao S3 e S4 sejam, as expressoes Booleanas estarao precedidas de IF

2-
Por inducão estrutural sobre a estrutura do programa bem formado P. Nesse caso, utilizaremos como medida de inducao o numero de operadores (n) de P.
Todos os casos com n = 1 são provados por vacuidade.
Caso base: n = 2. Temos 4 possibilidades:

P = if B then{ S1}. Logo a expressão tem número igual de colchetes e o mesmo número de if por “{“ . Para que n = 2 entramos em uma das duas opções a seguir:
1. S1= skip. Então o número de ocorrências de “{“ e “}” é zero e portanto a afirmativa vale por vacuidade.
2. S1 = X. Como X é uma atribuição o numero de ocorrências “{“ e “}” é zero e