Skip navigation

A segunda prova irá exigir mais especificamente conhecimentos adquiridos entre os capítulos 5 e 7, inclusive, do livro Lógica para Ciência da Computação do Prof. João Nunes de Souza, lembrando que todo o conhecimento prévio também é exigido, uma vez que é utilizado nas definições e ferramentas.

Em Adição, será exigido também conhecimento em portas lógicas, funções e circuitos lógicos e simplificação de funções/circuitos lógicos utilizando a álgebra booleana ou mapas de Karnaugh.

Para essa ementa consulte as seguintes fontes na internet:

http://www.estgv.ipv.pt/PaginasPessoais/ffrancisco/sd0506/05km.pdf

http://www.inf.ufsc.br/~guntzel/isd/isd2.pdf

http://dcm.ffclrp.usp.br/~augusto/teaching/aba/AB-Funcoes-Logicas-Portas-Logicas.pdf

http://www.feng.pucrs.br/~decastro/pdf/ED_C1.pdf

http://www.inf.ufsc.br/ine5365/clteoria.html

http://pt.slideshare.net/thild/simplificacao-mapas-karnaugh

Bons Estudos.

Fig 9.1:

wpid-01_-2014-11-24-12-251.png

Fig 9.2:

wpid-02_-2014-11-24-12-251.png

Fig 9.3

wpid-03_-2014-11-24-12-251.png

Fig. 9.4

wpid-04_-2014-11-24-12-251.png

Fig 9.5

wpid-05_-2014-11-24-12-251.png

Fig 9.6

wpid-06_-2014-11-24-12-251.png

Fig 9.7

wpid-07_-2014-11-24-12-251.png

Fig 9.8

wpid-08_-2014-11-24-12-251.png

Fig 9.9

wpid-09_-2014-11-24-12-251.png

Fig 9.10

wpid-10_-2014-11-24-12-251.png

Fig 9.11

wpid-11_-2014-11-24-12-251.png

Fig 9.12

Fig 9.13

wpid-13_-2014-11-24-12-25.png

Fig 9.14

wpid-14_-2014-11-24-12-25.png

Fig 9.16

wpid-15_-2014-11-24-12-25.png

Fig 9. 17

wpid-16_-2014-11-24-12-25.png

Fig 9.18

wpid-17_-2014-11-24-12-25.png

Fig 9.19

wpid-18_-2014-11-24-12-25.png

Fig 9.20

wpid-19_-2014-11-24-12-25.png

Expressões

Utilizadas para retornar um cálculo no SQL

Exemplo:

Q13) Listar o nome e os salários resultantes de um aumento

de 10% para os funcionários do projeto ’Productx’

SELECT fname, minit, lname, salary*1.1 as NewSalary

FROM employee, project, works_on

WHERE ssn=essn AND pno=pnumber

AND pname=’ProductX’

Cláusula BETWEEN

Retorna os dados entre intervalos fechados definidos.

Q14) Listar todos os empregados no departamento 5 cujo

salário está entre 30000 e 40000

SELECT *

FROM employee

WHERE dno=’5’

AND salary BETWEEN 30000 AND 40000

Cláusula Order By

Ordena o resultado pela(s) coluna(s) escolhida(s), da maneira desejada: Ascendente ou Descendente

Q 15) Listar os empregados e projetos em que eles estão

trabalhando, ordenados pelo departamento e, dentro de

cada departamento, ordenado pelo último e primeiro nome

SELECT dno, fname, lname, pno

FROM employee, works_on

WHERE essn=ssn

ORDER BY dno, fname, lname

Consultas Complexas

  • consultas aninhadas e comparação de conjuntos
  • tabelas obtidas de junção
  • funções de agregação
  • cláusulas “group by” e having
Cláusula IN (pertinência)

A consulta Q4 abaixo pode ser reformulada, removendo a cláusula UNION e incluindo a cláusula IN

Q4) Listar todos os números de projetos que envolvam um empregado cujo último nome é ’Smith’ sendo que o empregado deve ser trabalhador ou gerente do departamento que controla o projeto.

(SELECT DISTINCT pnumber FROM project, department, employee

WHERE dnum=dnumber AND msgrssn=ssn AND lname=’Smith’)

UNION

(SELECT DISTINCT pnumber FROM project, works_on, employee

WHERE pno=pnumber AND essn=ssn AND lname=’Smith’)

SELECT DISTINCT pnumber FROM project

WHERE pnumber IN

(SELECT pnumber FROM project, department, employee

WHERE dnum=dnumber AND mgrssn=ssn

AND lname=’Smith’)

OR pnumber IN

(SELECT pno FROM works on,employee

WHERE essn=ssn AND lname=’Smith’);

Comparando conjuntos com ALL, ANY ou SOME

Outras cláusulas para comparação de conjuntos:

ALL

ANY ou SOME (são sinônimos)

Ex: salary > ALL (SELECT salary FROM …);

salary < ANY (SELECT salary FROM …);

salary > SOME (SELECT salary FROM …);

Ambiguidade em consultas aninhadas – (apelidos de tabelas)

Q16) Listar o nome dos empregados com dependente(s) de mesmo ’first name’ e sexo que o empregado

SELECT e.fname,e.lname

FROM employee as e

WHERE e.ssn IN

(SELECT essn FROM dependent as d

WHERE fname=dependent_name

AND e.sex=d.sex);

SELECT e.fname,e.lname

FROM employee as e, dependent as d

WHERE ssn=essn

AND fname=dependent_name

AND e.sex=d.sex;

FUNÇÃO EXISTS – consultas aninhadas correlacionadas

Q16b) Listar o nome dos empregados com dependente(s) de mesmo ’first name’ e sexo que o empregado

SELECT e.fname,e.lname

FROM employee as e

WHERE EXISTS

(SELECT * FROM dependent d

WHERE e.ssn=d.essn

AND e.fname=d.dependent_name

AND e.sex=d.sex);

FUNÇÃO NOT EXISTS – consultas aninhadas correlacionadas

Q6) Listar os nomes de empregados sem dependentes

SELECT fname,lname

FROM employee

WHERE NOT EXISTS (SELECT *

FROM dependent

WHERE ssn=essn);

Aninhamento em dois níveis

Q3b) Listar o nome dos empregados que trabalham em todos

os projetos controlados pelo departamento número 4

OBS: Observe a expressão todos no enunciado da consulta. Esta é a divisão da álgebra relacional. Em SQL a divisão pode ser especificada de diversas formas.

SELECT lname, fname FROM employee

WHERE NOT EXISTS

(SELECT * FROM project WHERE dnum=4

AND NOT EXISTS

(SELECT * FROM works_on

WHERE essn=ssn

AND pnumber=pno));

Alternativas de Divisão para SQL

Alternativas de especificação de divisão em SQL:

 Usando cláusulas NOT EXISTS e IN

 Usando cláusula NOT EXISTS e EXCEPT

 Usando cláusula FOREACH e EXISTS(não implementada no PostgreSql 8.3)

divisão usando cláusulas NOT EXISTS e IN

SELECT lname, fname FROM employee

WHERE NOT EXISTS

(SELECT * FROM works_on w1

WHERE (w1.pno IN (SELECT pnumber FROM

project WHERE dnum=4))

AND NOT EXISTS

(SELECT * FROM works_on w2

WHERE w2.ecpf=cpf AND w2.pno=w1.pno));

divisão usando cláusulas NOT EXISTS e EXCEPT

SELECT lname, fname FROM employee e

WHERE NOT EXISTS

(SELECT pnumber FROM project WHERE dnum=4

EXCEPT

(SELECT pno FROM works_on w

WHERE w.ecpf=e.cpf))

divisão usando cláusulas FOREACH e EXISTS

SELECT lname, fname FROM employee

WHERE FOREACH

(SELECT pnumber FROM project WHERE dnum=4)

EXISTS

(SELECT * FROM works_on

WHERE ecpf=cpf AND pno=pnumber));

ATENÇÃO: este comando não funciona no PostgreSql 8.3

Tabelas obtidas de junção

Q1a) Listar o nome e endereço dos empregados que

trabalham no departamento ’Research’

SELECT fname, minit, lname, address, dnumber

FROM (employee JOIN department ON dno=dnumber)

WHERE dname=’Research’

Junção Natural

Na junção natural iguala-se atributos de mesmo nome

Qlb)Listar o nome e endereço dos empregados que trabalham no departamento ’Research’

SELECT fname, name, address

FROM (employee NATURAL JOIN

(department AS dept (dname, dno, mssn,

msdate)))

WHERE dname= ’Research’

OUTER JOIN

A cláusula {LEFT | FULL | RIGHT} OUTER JOIN mantêm no resultado todas as tuplas da tabela da esquerda, das duas tabelas ou da tabela da direita da junção, respectivamente, inserindo NULL quando não há casamento (matching)

Q8b)Para cada empregado, liste o seu primeiro acompanhado do primeiro nome de seu supervisor, mesmo se o empregado não tiver supervisor, liste seu nome

SELECT e.fname as employee_name,

s.fname as supervisor_name

FROM (employee AS e LEFT OUTER JOIN

employee AS s ON e.supercpf =s.cpf)

Exemplo Q8b’)

Q8b’)Liste o primeiro nome do supervisor e o primeiro nome de seus supervisionado, ordenado pelo primeiro. Mesmo se o empregado não for supervisor de ninguém, liste seu nome na primeira coluna e mesmo se o empregado não tiver supervisor, liste seu nome na segunda coluna.

SELECT s.fname as supervisor_name,

e.fname as employee_name

FROM (employee AS e FULL OUTER JOIN

employee AS s ON e.supercpf =s.cpf)

ORDER BY 1

Junções aninhadas

Q2a) Para todo projeto localizado em ’Stafford’, listar o número do projeto, o número do departamento que o controla e o último nome do gerente do departamento

SELECT pnumber, dnum, lname

FROM ((project JOIN department ON dnum=dnumber

(JOIN employee ON mgrssn=ssn))

WHERE plocation = ’Stafford’

Funções de agregação

• COUNT

• SUM

• MAX

• MIN

• AVG

• etc.

Exemplo Q19

Q19) Listar a soma de salários de todos os empregados,o maior salário e a média de salários

SELECT

SUM(salary), MAX(salary), MIN(salary) AVG(salary)

FROM employee;

Q20) Listar a soma de salários, o maior salário e a média de salários, somente para funcionários do departamento ‘Research’

SELECT

SUM(salary), MAX(salary), MIN(salary), AVG(salary)

FROM employee, department

WHERE dno=dnumber AND dname=’Research’;

Q21) Listar o número de empregados

SELECT COUNT(*) FROM employee;

Q23) Listar o número de salários distintos

SELECT COUNT(DISTINCT salary) FROM employee;

Funções de agregação em subconsultas

Q5) Listar o nome dos empregados que têm dois ou mais dependentes

SELECT lname, fname

FROM employee

WHERE (SELECT COUNT(*)

FROM dependent

WHERE essn=ssn) >= 2;

Cláusulas group by

Q24) Listar para cada departamento seu número, a quantidade de empregados e a média salarial de seus empregados

SELECT dnumber, COUNT(*), AVG(salary)

FROM department, employee

WHERE dno=dnumber

GROUP BY dnumber;

OBS: o agrupamento deve incluir todas as colunas da projeção que não incluem função de agregação

Group by com duas colunas

Q25) Listar para cada projeto seu número, nome e a quantidade de empregados que trabalham no projeto.

SELECT pnumber, pname, COUNT(*)

FROM project, works_on

WHERE pno=pnumber

GROUP BY pnumber, pname;

Cláusulas group by e having

Q26) Listar para cada projeto onde trabalham mais de dois empregados seu número e a quantidade de empregados que trabalham no projeto

SELECT pnumber, pname, COUNT(*)

FROM project, works_on

WHERE pno=pnumber

GROUP BY pnumber, pname

HAVING COUNT (* )> 2;

Cláusulas group by e consultas aninhadas com cláusula IN

Q28) Listar para cada departamento que tem mais que 5 empregados, o número do departamento e o número de empregados que ganham mais que 40000

SELECT dno, COUNT(*)

FROM employee

WHERE salary > 40000

AND dno IN

(SELECT dnumber FROM department

WHERE(SELECT COUNT(*)

FROM employee e2

WHERE e2 .dno=dnumber)>5)

SQL/DML e o PostgreSQL

EXERCÍCIOS DE IMPLEMENTAÇÃO

=> Exercícios de consultas simples no esquema company

=> Exercicios de consultas complexas no esquema company e exercícios usando o esquema SEE

Bibliografia:

[SK] Capítulos 3,4,5

Expressões

Utilizadas para retornar um cálculo no SQL

Exemplo:

Q13) Listar o nome e os salários resultantes de um aumento

de 10% para os funcionários do projeto ’Productx’

SELECT fname, minit, lname, salary*1.1 as NewSalary

FROM employee, project, works_on

WHERE ssn=essn AND pno=pnumber

AND pname=’ProductX’

Cláusula BETWEEN

Retorna os dados entre intervalos fechados definidos.

Q14) Listar todos os empregados no departamento 5 cujo

salário está entre 30000 e 40000

SELECT *

FROM employee

WHERE dno=’5’

AND salary BETWEEN 30000 AND 40000

Cláusula Order By

Ordena o resultado pela(s) coluna(s) escolhida(s), da maneira desejada: Ascendente ou Descendente

Q 15) Listar os empregados e projetos em que eles estão

trabalhando, ordenados pelo departamento e, dentro de

cada departamento, ordenado pelo último e primeiro nome

SELECT dno, fname, lname, pno

FROM employee, works on

WHERE essn=ssn

ORDER BY dno, fname, lname

Consultas Complexas

  • consultas aninhadas e comparação de conjuntos
  • tabelas obtidas de junção
  • funções de agregação
  • cláusulas “group by” e having
Cláusula IN (pertinência)

A consulta Q4 abaixo pode ser reformulada, removendo a cláusula UNION e incluindo a cláusula IN

Q4) Listar todos os números de projetos que envolvam um empregado cujo último nome é ’Smith’ sendo que o empregado deve ser trabalhador ou gerente do departamento que controla o projeto.

(SELECT DISTINCT pnumber FROM project, department, employee

WHERE dnum=dnumber AND msgrssn=ssn AND lname=’Smith’)

UNION

(SELECT DISTINCT pnumber FROM project, works_on, employee

WHERE pno=pnumber AND essn=ssn AND lname=’Smith’)

SELECT DISTINCT pnumber FROM project

WHERE pnumber IN

(SELECT pnumber FROM project, department, employee

WHERE dnum=dnumber AND mgrssn=ssn

AND lname=’Smith’)

OR pnumber IN

(SELECT pno FROM works on,employee

WHERE essn=ssn AND lname=’Smith’);

Comparando conjuntos com ALL, ANY ou SOME

Outras cláusulas para comparação de conjuntos:

ALL

ANY ou SOME (são sinônimos)

Ex: salary > ALL (SELECT salary FROM …);

salary < ANY (SELECT salary FROM …);

salary > SOME (SELECT salary FROM …);

Ambiguidade em consultas aninhadas – (apelidos de tabelas)

Q16) Listar o nome dos empregados com dependente(s) de mesmo ’first name’ e sexo que o empregado

SELECT e.fname,e.lname

FROM employee as e

WHERE e.ssn IN

(SELECT essn FROM dependent as d

WHERE fname=dependent_name

AND e.sex=d.sex);

SELECT e.fname,e.lname

FROM employee as e, dependent as d

WHERE ssn=essn

AND fname=dependent_name

AND e.sex=d.sex);

FUNÇÃO EXISTS – consultas aninhadas correlacionadas

Q16b) Listar o nome dos empregados com dependente(s) de mesmo ’first name’ e sexo que o empregado

SELECT e.fname,e.lname

FROM employee as e

WHERE EXISTS

(SELECT * FROM dependent d

WHERE e.ssn=d.essn

AND e.fname=d.dependent_name

AND e.sex=d.sex);

FUNÇÃO NOT EXISTS – consultas aninhadas correlacionadas

Q6) Listar os nomes de empregados sem dependentes

SELECT fname,lname

FROM employee

WHERE NOT EXISTS (SELECT *

FROM dependent

WHERE ssn=essn);

Aninhamento em dois níveis

Q3b) Listar o nome dos empregados que trabalham em todos

os projetos controlados pelo departamento número 4

OBS: Observe a expressão todos no enunciado da consulta. Esta é a divisão da álgebra relacional. Em SQL a divisão pode ser especificada de diversas formas.

SELECT lname, fname FROM employee

WHERE NOT EXISTS

(SELECT * FROM project WHERE dnum=4

AND NOT EXISTS

(SELECT * FROM works_on

WHERE essn=ssn

AND pnumber=pno));

Alternativas de Divisão para SQL

Alternativas de especificação de divisão em SQL:

 Usando cláusulas NOT EXISTS e IN

 Usando cláusula NOT EXISTS e EXCEPT

 Usando cláusula FOREACH e EXISTS(não implementada no PostgreSql 8.3)

divisão usando cláusulas NOT EXISTS e IN

SELECT lname, fname FROM employee

WHERE NOT EXISTS

(SELECT * FROM works_on w1

WHERE (w1.pno IN (SELECT pnumber FROM

project WHERE dnum=4))

AND NOT EXISTS

(SELECT * FROM works_on w2

WHERE w2.essn=ssn AND w2.pno=w1.pno));

divisão usando cláusulas NOT EXISTS e EXCEPT

SELECT lname, fname FROM employee e

WHERE NOT EXISTS

(SELECT pnumber FROM project WHERE dnum=4

EXCEPT

(SELECT pno FROM works_on w

WHERE w.essn=e.ssn))

divisão usando cláusulas FOREACH e EXISTS

SELECT lname, fname FROM employee

WHERE FOREACH

(SELECT pnumber FROM project WHERE dnum=4)

EXISTS

(SELECT * FROM works_on

WHERE essn=ssn AND pno=pnumber));

ATENÇÃO: este comando não funciona no PostgreSql 8.3

Tabelas obtidas de junção

Q1a) Listar o nome e endereço dos empregados que

trabalham no departamento ’Research’

SELECT fname, minit, lname, address

FROM (employee JOIN department ON dno=dnumber)

WHERE dname=’Research’

Junção Natural

Na junção natural iguala-se atributos de mesmo nome

Qlb)Listar o nome e endereço dos empregados que trabalham no departamento ’Research’

SELECT fname, name, address

FROM (employee NATURAL JOIN

(department AS dept (dname, dno, mssn,

msdate)))

WHERE dname= ’Research’

OUTER JOIN

A cláusula {LEFT | FULL | RIGHT} OUTER JOIN mantêm no resultado todas as tuplas da tabela da esquerda, das duas tabelas ou da tabela da direita da junção, respectivamente, inserindo NULL quando não há casamento (matching)

Q8b)Para cada empregado, liste o seu primeiro acompanhado do primeiro nome de seu supervisor, mesmo se o empregado não tiver supervisor, liste seu nome

SELECT e.fname as employee_name,

s.fname as supervisor_name

FROM (employee AS e LEFT OUTER JOIN

employee AS s ON e.superssn =s.ssn)

Exemplo Q8b’)

Q8b’)Liste o primeiro nome do supervisor e o primeiro nome de seus supervisionado, ordenado pelo primeiro. Mesmo se o empregado não for supervisor de ninguém, liste seu nome na primeira coluna e mesmo se o empregado não tiver supervisor, liste seu nome na segunda coluna.

SELECT s.fname as supervisor_name,

e.fname as employee_name

FROM (employee AS e FULL OUTER JOIN

employee AS s ON e.superssn =s.ssn)

ORDER BY 1

Junções aninhadas

Q2a) Para todo projeto localizado em ’Stafford’, listar o número do projeto, o número do departamento que o controla e o último nome do gerente do departamento

SELECT pnumber, dnum, lname

FROM ((project JOIN department ON dnum=dnumber

(JOIN employee ON mgrssn=ssn))

WHERE plocation = ’Stafford’

Funções de agregação

• COUNT

• SUM

• MAX

• MIN

• AVG

• etc.

Exemplo Q19

Q19) Listar a soma de salários de todos os empregados,o maior salário e a média de salários

SELECT

SUM(salary), MAX(salary), MIN(salary) AVG(salary)

FROM employee;

Q20) Listar a soma de salários, o maior salário e a média de salários, somente para funcionários do departamento ‘Research’

SELECT

SUM(salary), MAX(salary), MIN(salary), AVG(salary)

FROM employee, department

WHERE dno=dnumber AND dname=’Research’;

Q21) Listar o número de empregados

SELECT COUNT(*) FROM employee;

Q23) Listar o número de salários distintos

SELECT COUNT(DISTINCT salary) FROM employee;

Funções de agregação em subconsultas

Q5) Listar o nome dos empregados que têm dois ou mais dependentes

SELECT lname, fname

FROM employee

WHERE (SELECT COUNT(*)

FROM dependent

WHERE essn=ssn) >= 2;

Cláusulas group by

Q24) Listar para cada departamento seu número, a quantidade de empregados e a média salarial de seus empregados

SELECT dnumber, COUNT(*), AVG(salary)

FROM department, employee

WHERE dno=dnumber

GROUP BY dnumber;

OBS: o agrupamento deve incluir todas as colunas da projeção que não incluem função de agregação

Group by com duas colunas

Q25) Listar para cada projeto seu número, nome e a quantidade de empregados que trabalham no projeto.

SELECT pnumber, pname, COUNT(*)

FROM project, works_on

WHERE pno=pnumber

GROUP BY pnumber, pname;

Cláusulas group by e having

Q26) Listar para cada projeto onde trabalham mais de dois empregados seu número e a quantidade de empregados que trabalham no projeto

SELECT pnumber, pname, COUNT(*)

FROM project, works_on

WHERE pno=pnumber

GROUP BY pnumber, pname

HAVING COUNT (* )> 2;

Cláusulas group by e consultas aninhadas com cláusula IN

Q28) Listar para cada departamento que tem mais que 5 empregados, o número do departamento e o número de empregados que ganham mais que 40000

SELECT dno, COUNT(*)

FROM employee

WHERE salary > 40000

AND dno IN

(SELECT dnumber FROM department

WHERE(SELECT COUNT(*)

FROM employee e2

WHERE e2 .dno=dnumber)>2)

SQL/DML e o PostgreSQL

EXERCÍCIOS DE IMPLEMENTAÇÃO

=> Exemplos de consultas simples no esquema company

=> Exemplos de consultas complexas no esquema company e exercícios usando o esquema SEE

Bibliografia:

[SK] Capítulos 3,4,5

Os comandos da Linguagem de Modelagem de Dados do SQL são responsáveis por:

– Comandos de inserção de tuplas em tabelas

– Comandos de alteração e supressão de tuplas

– Comandos de consulta (básicos e complexos)

Def. A SQL/DML(Data Manipulation Language) é um subconjunto da SQL usada para recuperar, inserir, atualizar e suprimir dados de tabelas do BD.

• INSERT – inserção de linhas;

• DELETE – supressão de linhas;

• UPDATE – atualização de dados;

• SELECT – recuperação de tabelas;

OBS: serão mostradas características do padrão SQL implementadas pelo PostgreSQL, omitindo funcionalidades adicionais e destacando eventuais omissões.

Insert

INSERT INTO tabela [ ( coluna [, …] ) ]

{ DEFAULT VALUES

|VALUES ( { expressão | DEFAULT } [, …] )

[, …]

| comando-select

}

Exemplo 1

INSERT INTO tabela VALUES (expressão [, …] )

INSERT INTO employee

VALUES (‘John’, ‘B’, ‘Smith’, ‘123456789’,

DATE ‘1965-01-09’, ‘731 Fondren, Houston, TX’,

‘M’, 30000, ‘333445555’, 5);

Compatibilidade de tipos:

employee (fname VARCHAR (15) NOT NULL,

minit CHAR, lname VARCHAR (15) NOT NULL,

ssn CHAR(9) PRIMARY KEY, bdate DATE,

address VARCHAR(30), sex CHAR CHECK (sex IN (’M’, ’F’)),

salary DECIMAL(10,2), superssn CHAR(9), dno INT NOT NULL)

Exemplo 2

INSERT INTO tabela ( coluna [, …] )

VALUES (expressão [, …] )

INSERT INTO employee(fname, minit, lname, ssn, dno)

VALUES (‘John’, ‘B’, ‘Smith’, ‘123456789’, 5);

Exemplo 3

INSERT INTO tabela comando-select

INSERT INTO works_on

SELECT ssn, pnumber, 0

FROM employee, project;

Delete

DELETE FROM tabela [ [ AS ] alias ]

[ WHERE condição

| WHERE CURRENT OF cursor_name ]

DELETE FROM employee WHERE ssn = ‘123456789’

OBS: o uso de cursores será visto posteriormente

Update

UPDATE tabela [ [ AS ] alias ]

SET {coluna = { expresssão | DEFAULT }

| ( coluna [, …] ) =

( { expressão | DEFAULT } [, …] )

} [, …]

[ WHERE condição

| WHERE CURRENT OF cursor_name ]

OBS: o uso de cursores será visto posteriormente

Update Exemplo 1

UPDATE employee

SET address = ‘Av. Joao Naves de Avila, 2121’,

salary = salary * 1.5

WHERE ssn = ‘123456789’

Update Contra-Exemplo

UPDATE works_on

SET (pno, hours) =

(SELECT pnumber, 10

FROM project WHERE pnumber = 1)

WHERE essn=’123456789′;

OBS: o padrão permite associação de uma lista de atributos com uma tupla resultante da saída de uma consulta, mas isto não foi implementado pelo PostgreSql 8.3, onde as expressões devem ser independentes. Logo o comando acima não funciona no PostgreSql 8.3 (teste isso nas versões mais recentes)

Update Exemplo 2

UPDATE works_on

SET (pno, hours) = (1, 10)

WHERE essn=’123456789′;

Select

SELECT [ALL | DISTINCT]

* | expressão [ AS nome_saida ] [, …]

FROM item_from [, …]

[ WHERE condição ]

[ GROUP BY expressão [, …] ]

[ HAVING condição [, …] ]

[ { UNION | INTERSECT | EXCEPT } [ ALL ] select ]

[ ORDER BY expressão [ ASC | DESC | USING operador ]

[ NULLS { FIRST | LAST } ] [, …] ]

[ FOR { UPDATE | SHARE }

[ OF nome_tabela [, …] ] [ NOWAIT ] […] ]

–Consultas básicas e complexas

Considerando os diversos parâmetros do comando SELECT,

para efeito didático, vamos dividir nosso estudo em:

 consultas básicas: na condição do WHERE não existe

outro SELECT

 consultas complexas: são consultas aninhadas, onde na

condição do SELECT existe outra cláusula SELECT.

SELECT-FROM-WHERE

Formato de comando SELECT para consultas básicas:

SELECT lista-de-atributos

FROM lista-de-tabelas

WHERE condição

OBS:

– condições sem cláusula SELECT;

– os exemplos a seguir seguem a numeração de EN e estão

baseados no BD company;

Restrição + Projeção

QO) Listar a data de nascimento e o endereço dos

empregados com nome : John B. Smith.

SELECT bdate, address

FROM employee

WHERE fname=’John’

AND minit=’B’

AND lname=’Smith’;

Restrição + Projeção + Junção

Q1) Listar o nome e endereço dos empregados que trabalham

no departamento ’Research

SELECT fname, minit, lname, address

FROM employee, department

WHERE dno=dnumber AND dname=’Research’

Junção com duas condições

Q2) Para todo projeto localizado em ’Stafford’, listar o

número do projeto, o número do departamento que o

controla e o último nome, endereço e data de nascimento

do gerente do departamento.

SELECT pnumber, dnum, lname, address, bdate

FROM project, department, employee

WHERE plocation=’Stafford’

AND dnum=dnumber

AND ssn=mgrssn

Ambiguidade de nomes de atributos

Suponha que DNUMBER e NAME são os nomes dos

atributos DNO e LNAME em EMPLOYEE,

respectivamente. Além disso, suponha que NAME é o

nome do atributo DNAME em DEPARTMENT.

Então:

employee(fname, minit, name, ssn, bdate, address, sex,

salary, superssn, dnumber)

department(name, dnumber, mgrssn, mgrstartdate)

Qualificando atributos

Q1a) Listar o nome e endereço dos empregados que

trabalham no departamento ’Research’ considerando os

esquemas abaixo

employee(fname, minit, name, ssn, bdate, address, sex,

salary, superssn, dnumber)

department(name, dnumber, mgrssn, mgrstartdate)

SELECT fname, minit, employee.name

FROM employee, department

WHERE employee.dnumber=department.dnumber

AND department.name=’Research’

Apelidos de Tabelas (Renomeação)

Q8) Para cada empregado, liste o seu primeiro e o seu último

nome acompanhados do último nome de seu supervisor.

SELECT e.fname, e.lname, s.lname

FROM employee AS e, employee AS s

WHERE e.superssn=s.ssn

Q1b’) Listar o nome e o endereço dos empregados que

trabalham no departamento ’Research’ considerando as

novas tabelas employee e department e usando apelidos

SELECT fname, minit, e.name, address

FROM employee e, department d

WHERE e.dnumber=d.dnumber

AND d.name=’Research’

Exemplo Q1c–Omitindo WHERE e uso do * para consulta sem projeção

Qlc’) Listar todos os valores de atributos de todos os empregados

SELECT * FROM employee

Produto Cartesiano

Q1Ob) Listar o produto cartesiano de empregados e departamentos

SELECT *

FROM employee, department

Tabela x relação// multset ou bags x set // Cláusula DISTINCT

Q11a) Listar todos os salários distintos

SELECT DISTINCT salary

FROM employee

Cláusula UNION

Q4) Listar todos os números de projetos que envolvam um

empregado cujo último nome é ’Smith’ sendo que o

empregado deve sertrabalhador ou gerente do

departamento que controla o projeto.

(SELECT DISTINCT pnumber

FROM project, department, employee

WHERE dnum=dnumber AND msgrssn=ssn AND lname=’Smith’)

UNION

(SELECT DISTINCT pnumber

FROM works_on, employee

WHERE essn=ssn AND lname=’Smith’)

Cláusula LIKE

Q12) Listar o nome de todo empregado cujo endereço está

em Houston, Texas

SELECT fname, minit, lname

FROM employee

WHERE address LIKE ’%Houston%TX%’

Like usando underline _

Q12a) Listar o nome de todos os empregados nascidos na

década de 50

SELECT fname, minit, lname

FROM employee

WHERE bdate LIKE ’_ _ 5%’

Considerando o DER desenvolvido no trabalho anterior:

Faça o mapeamento do DER anterior para o modelo relacional, incluindo as restrições de chave, integridade referencial e de domínio.

Desenhe um DER para o Sistema de Eventos Esportivos descrito abaixo

O SEE tem como objetivo armazenar dados de modalidades esportivas (ex: Natação), categorias (ex: 100m costas), competições,locais, pessoas e equipes participeantes,. Além disso, armazenar dados de empresas patrocinadoras e resultados das competições.

Uma categoria deve ter nome, tipo (individual ou coletiva) e gênero. Cada competição tem uma data, horário, local e refere-se a uma fase da categoria, sendo que deve existir pelo menos uma fase final por categoria.

Os atletas ou equipes se inscrevem em categorias e participam de competições. Cada atleta (ou equipe) terá um resultado nba competição, incluindo um escore e uma indicação de colocação na competição e na categoria. O vencedor da competição final será o vencedor da categoria. Cada local terá um endereçou, capacidade de público e lista de modalidades esportivas. As pessoas terão CPF, nome, idade e serão do tipo funcionário ou atleta. Dos atletas deve-se registrar as categorias inscritas. Os funcionários podem ser responsáveis por locais. Cada local deve ter um responsável. O árbitro é um tipo especial de funcionário para o qual deve-se registrar as modalidades. Cada equipe terá um nome e uma lista de atletas participantes. Cada empresa patrocinadora terá um cnpj, nome, endereço e tipo de patrocínio (atleta, equipe e/ou evento). Nos dois primeiros casos deve-se registrar quem são os patrocinados, no último caso deve-se régistrar o valor do patrocínio.

  • deduzir dependências funcionais a partir de um conjunto dado;
  • junção sem perda e preservação de dependências funcionais;
  • projeto relacional por síntese;

 

Fecho de DF – F+
Seja F o conjunto de dependências funcionais que são especificadas no esquema de relação R, o conjunto de todas as dependências que incluem F e todas as dependências que podem ser deduzidas de F, é chamado de fechamento de F, ou fecho de F, sendo denotado por F+.
Obs.: uma DF X → Y é deduzida de um conjunto de dependências F especificado em R, SE:
Sempre que r satisfizer todas as dependências em F,  ENTÃO X → Y também se mantém em r.

 

Fecho de DF – F+ – Exemplo
F = {(Dep_nr → Cpf_gerente), (Cpf_gerente → Telefone_ger)}
F |= (Dep_ nr → Telefone_ger); % Lê-se: de F deduzimos…
Como não há mais DF a deduzir de F, temos que:
F+ = F ∪ {(Dep_ nr → Telefone_ger)}

 

Regras de inferência em DF

Captura de Tela 2014-09-24 às 20.50.22

 

Fecho de X sob F – X+

Captura de Tela 2014-09-24 às 20.52.40

 

X+ sob F – Exemplo

 

Captura de Tela 2014-09-24 às 20.53.40

Equivalência de conjuntos de DF

 

Captura de Tela 2014-09-24 às 20.54.28

 

Equivalência de conjuntos de DF –
Exemplo/Exercício calcule F+ e G+

 

 

Captura de Tela 2014-09-24 às 20.55.38

 

Conjunto mínimo de DF

 

Captura de Tela 2014-09-24 às 20.56.02

 

Cobertura mínima de F

 

Captura de Tela 2014-09-24 às 20.57.11

 

Alg. 16.2 – Cobertura mínima de F
Alg. 16.2a – Chave

Captura de Tela 2014-09-24 às 21.05.08

 

Decomposição de R

O conjunto F de dependências funcionais que devem ser mantidas nos atributos de R é especificado pelos projetistas de banco de dados e se torna disponível aos algoritmos de projeto.
Ao utilizar as dependências funcionais, os algoritmos decompõem o esquema de relação universal R em um conjunto de esquemas de relação D = {R1, R2, …, Rm}, que se tornará o esquema do banco de dados relacional; D é chamado de decomposição de R.

 

Preservação de atributo

D = {R1, R2, …, Rm}, temos de garantir que cada atributo em R aparecerá em pelo menos um esquema de relação Ri na decomposição, de modo que nenhum atributo seja perdido. Formalmente, temos

Captura de Tela 2014-09-24 às 21.09.52

Esta é chamada de condição de preservação de atributo de uma decomposição.

 

Preservação de dependência – Intuição

Seria útil se cada dependência funcional X→Y especificada em F aparecesse diretamente em um dos esquemas de relação Ri na decomposição D ou pudesse ser deduzida das dependências que aparecem em alguma Ri.
Informalmente, essa é a condição de preservação de dependência

 

Preservação de dependência – Definição

Captura de Tela 2014-09-24 às 21.11.17

 

Preservação de dependência e 3FN

 

Captura de Tela 2014-09-24 às 21.13.09

 

Junção sem perda (não aditiva)

Captura de Tela 2014-09-24 às 21.14.23

Alg. 16.3 – Testa junção não aditiva 

 

Captura de Tela 2014-09-24 às 21.16.31

 

Captura de Tela 2014-09-24 às 21.17.17

 

Teste de junção não aditiva para
decomposições binárias

 

Captura de Tela 2014-09-24 às 21.18.12

 

 

Decomposições sucessivas

Captura de Tela 2014-09-24 às 21.18.51

 

Preservação de dependência e 3FN

O Algoritmo 16.4, a seguir, cria uma decomposição de preservação de dependência D = {R1, R2, …, Rm} de uma relação universal R com base em um conjunto de dependências funcionais F, tal que cada Ri em D está na 3FN.
Isso garante apenas a propriedade de preservação de dependência; mas não garante a propriedade de junção não aditiva.

 

Alg. 16.4 – Síntese para 3FN com preservação de dependência

Captura de Tela 2014-09-24 às 21.20.32

 

 

 

Motivação: alguns problemas de redundância não
são detectados pelas DF
Então, outras dependências são definidas, por
exemplo:
 Dependências Multivaloradas
 Dependências de Junção
 Dependências de Inclusão

 

Dependência Multivalorada –  O Problema

Seja a relação CPL(curso, professor, livro), onde:
– O professor P pode lecionar o curso C
– O livro L é recomendado para o curso C

Captura de Tela 2014-09-24 às 19.15.07

Chave é CPL

Livros e professores são independentes

Está na FNBC, mas há redundância

Sugere outra FN que nos leve a normalização de CPL para CP e CL

 

Dependência Multivalorada – Intuição

Sejam r, R, X e Y conforme definido, a dependência multivalorada X → → Y é válida  sobre r de R se para cada valor de X em r está  associado um conjunto de valores de Y e esse  conjunto é independente dos valores de Z=R – (X∪ Y)

• Intuitivamente o valor de um atributo determina  um conjunto de valores de outro atributo!!!

 

Dependência Multivalorada – Definição

Captura de Tela 2014-09-24 às 19.17.44

 

15: as tuplas t1, t2, t3 e t4, não são necessariamente distintas.

 

Dependência Multivalorada-Exemplo 1

Captura de Tela 2014-09-24 às 19.19.18

 

Dependência Multivalorada–Exemplo 2

 

 

Captura de Tela 2014-09-24 às 19.20.05

 

Dependência Multivalorada – Definição alternativa

Se X → → Y Então
πYZ(σX=x(R))=πY(σX=x(R)) x πZ(σX=x(R)).
Garante que dado o valor de X os valores de Y e Z  são independentes.
Se existe ti com (X=A e Y=B) e existe tj com (X=A e Z=C) Então deve existir  tk com (X=A, Y=B e Z=C).

 

Dependência Multivalorada – Propriedades

• toda dependência funcional é dependência multivalorada mas o recíproca não é necessariamente verdadeira

• Se (X→ → Y) e (Z=R-X ∪ Y) então X → → Z
• Se Y for subconjunto de X ou R=(X ∪ Y) então a MVD (X → → Y) é trivial
• Se a MVD não for trivial, para garantir a MVD,  teremos que repetir valores em tuplas, gerando redundância…isto leva à 4FN

 

Quarta forma normal – 4FN

 

Captura de Tela 2014-09-24 às 19.22.29

Dependência de Junção

 

 

Captura de Tela 2014-09-24 às 19.22.56

 

Quinta forma normal – 5FN

Captura de Tela 2014-09-24 às 19.24.04

 

Dependência de Junção – Exemplo

 

Exemplo: Seja X = (ecod, pno) e Y=(ecod, place)
e SKILL = X natural join Y

● DJ(X, Y) é uma dependência de junção em SKILL
● SKILL (ecod, pno, place) não está na 5FN pois X e Y não contêm uma superchave de SKILL
● Como vimos anteriormente, SKILL sequer está na 4FN. De fato a dependência multivalorada é um caso particular de dependência de junção, generalizando: DJ(X, Y) ≡ (X∩ Y) → → (X-Y)

Quinta forma normal – 5FN – Exemplo

Exemplo: está na 5FN
emp(ecod, ename, title)
proj(pno, pname, budget)
asg(ecod, pno, resp, dur)
pay(title, sal)
Obs: – uma relação na 5FN não pode ser decomposta sem perda de informação
– dependência de inclusão: define que algumas colunas estão contidas em outras. Chave estrangeira é um exemplo de dependência de inclusão

 

Normalização 2 – Considerações finais

A decomposição multivias para a 5FN é restrição semântica bastante peculiar e a normalização para a 5FN raramente é feita nestes termosUma alternativa à decomposição da relação universal é utilizar ferramentas de projeto conceitual e mapeamento para o relacional.
Por exemplo, um mapeamento do Modelo de Entidades e Relacionamentos para o Modelo Relacional gera esquemas de BD na terceira forma normal.

 

 

 

Identificação Formula H Fórmula G
Dupla Negativa ¬(¬E) E
Propriedades de Identidade
E ∨ False
E ∧ True

 

E
E

 

Propriedades Complementares
E ∨ ¬ E
E ∧ ¬ E
True
False
Leis de DeMorgan
¬(E ∧ R)
¬(E ∨ R)
¬E ∨ ¬R
¬E ∧ ¬R
Contraposição E → R ¬R → ¬E
Propriedades de Substituição
E → R
E ↔ R
¬E ∨ R
(E → R) ∧ (R → E)
Propriedades Comutativas
E ∨ R
E ∧ R
R ∨ E
R ∧ E
Propriedades Associativas
E ∨ (R ∨ S)
E ∧ (R ∧ S)
(E ∨ R) ∨ S
(E ∧ R) ∧ S
Propriedades Distributivas
E ∨ (R ∧ S)
E ∧ (R ∨ S)
(E ∨ R) ∧ (E ∨ S)
(E ∧ R) ∨ (E ∧ S)
Prova Condicional E → (R → S) (E ∧ R) → S

 

Exercício: Sejam P e Q ∈ L∅. Demonstre, com o auxílio das equivalências clássicas, que as fórmulas abaixo são equivalentes: E = Q → (Q ∧ P) e G = (¬Q ∨ Q) ∧ (¬Q ∨ P).
Solução: Q → (Q ∧ P)
 ⇔ ¬Q ∨ (Q ∧ P) (aplicando a Propriedade de Substituição do →)
 ⇔ (¬Q ∨ Q) ∧ (¬Q ∨ P) (aplicando a Propriedade Distributiva)
Métodos de Validação de Fórmulas
  • Tabela-Verdade
A tabela-verdade é um método de validação baseada na força bruta. Isso ocorre, porque devemos mapear todas as possíveis combinações dos símbolos/variáveis proposicionais.
Assim, seja P uma fórmula proposicional e α o conjunto de variáveis proposicionais existentes em P (α = {X1, X2, …, XN}). A tabela-verdade de P é uma tabela com pelo menos N+1 colunas e exatamente 2N linhas. As N primeiras colunas representam as variáveis proposicionais, enquanto a (N+1)-ésima coluna representa a fórmula P. Cada linha representa uma possível combinação de valores (T ou F) das variáveis pertencentes a α e o valor verdade de P resultante desta combinação.
TABELA-VERDADE X PROPRIEDADES SEMÂNTICAS
1- Uma fórmula é uma tautologia se a última coluna de sua tabela-verdade contém somente
valores T ou 1.
2- Uma fórmula é uma contradição se a última coluna de sua tabela-verdade contém somente
valores F ou 0 (zero).
3- Uma fórmula é factível se a última coluna de sua tabela-verdade contém pelo menos um valor
T ou 1.
4- Duas fórmulas são equivalentes semanticamente quando, para cada linha da tabela-verdade,
suas colunas apresentam o mesmo valor.
5- Uma fórmula G implica semanticamente na fórmula H se, para toda linha cujo valor da coluna
de G é verdadeiro, o valor da coluna de H também é verdadeiro.
  • Árvore Semântica
Este método determina a validade de uma fórmula a partir de uma estrutura denominada árvore.
Uma árvore é um conjunto de nós (vértices) ligados por arestas. Os nós finais são chamados “folhas”, o nó inicial é denominado “raiz”, enquanto os demais nós são intermediários.
Exemplo de Árvore:

Captura de Tela 2014-09-22 às 18.23.40

Durante a validação, as arestas que ligam o nó raiz aos outros nós recebem um rótulo, indicando os possíveis valores de uma determinada variável proposicional, escolhida aleatoriamente. Se a partir de uma interpretação for possível obter o valor da fórmula, este é associado ao nó folha correspondente. Caso não seja possível tal aferição, cria-se mais duas arestas, aumentando a ramificação da árvore. Para a rotulação dessas arestas, escolhemos uma outra variável proposicional. Este processo é repetido até que todos os nós folhas tenham valores associados à fórmula.

Exercício: Demonstre, através de árvores semânticas, a validade de H = (P → Q) ↔ (¬Q ∧ ¬P).
Solução:
Captura de Tela 2014-09-22 às 18.24.55
ÁRVORE SEMÂNTICA X PROPRIEDADES SEMÂNTICAS
1- Uma fórmula é uma tautologia se só têm valores T ou 1 em seus nós folhas.
2- Uma fórmula é uma contradição se só têm valores F ou 0 (zero) em seus nós folhas.
3- Uma fórmula é factível se pelo menos um nó folha com valor T ou 1.
4- Duas fórmulas G e H são equivalentes semanticamente, se a árvore semântica
correspondente à fórmula G ↔ H for uma tautologia.
5- Uma fórmula G implica semanticamente na fórmula H, se a árvore semântica correspondente
à fórmula G → H for uma tautologia.

 

  • Método da Negação ou Absurdo
O método da negação ou absurdo é um método geral de demonstração. Ele consiste em negar a afirmação que se deseja provar e, a partir de um conjunto de deduções, concluir um fato contraditório ou absurdo (ex: I[P] = T e I[P] = F).
A aplicação deste método é recomendada nos casos onde a negação da afirmação nos leva a casos determinísticos, ou seja, com uma única possibilidade de interpretação para a fórmula, pois isto simplifica a demonstração. Tal situação ocorre quando a negação acarreta a falsidade dos conectivos → e ∨ e a veracidade do conectivo ∧.
Exercício: Demonstrar, através do método da negação, a validade da Lei de Transitividade do
conectivo →: H = ((P → Q) ∧ (Q → R)) → (P → R)
Solução: validade = tautologia. Logo, devemos provar que ∀ I | I[H] = T.
 Supondo que H NÃO é tautologia, então ∃ I | I[H] = F.
I[((P → Q) ∧ (Q → R)) → (P → R)] = F ⇒ I[((P → Q) ∧ (Q → R))] = T e I[(P → R)] = F
 Para I[(P → R)] = F ⇒ I[P] = T e I[R] = F
 Para I[((P → Q) ∧ (Q → R))] = T ⇒ I[P → Q] = T e I[Q → R] = T
 Se I[P → Q] = T ⇒ I[P] = F e/ou I[Q] = T, mas como I[P] = T, logo:   I[Q] = T
 Se I[Q → R] = T ⇒ I[Q] = F e/ou I[R] = T, mas como I[R] = F, logo:   I[Q] = F
 ABSURDO: Q NÃO pode assumir dois valores (T e F) no mesmo instante.
Portanto, a suposição inicial está errada e H é tautologia.
O objetivo deste método é deduzir uma contradição / absurdo a partir da negação da fórmula em prova. Entretanto, nem sempre isto ocorre. Nestes casos, NADA se pode concluir sobre a veracidade da asserção inicial. Além disso, quando existem mais de uma possibilidade testada, originada de cláusulas e/ou, todas devem gerar uma contradição.
MÉTODO DA NEGAÇÃO OU ABSURDO X PROPRIEDADES SEMÂNTICAS
1- Uma fórmula H é uma tautologia se a suposição ∃ I | I[H] = F gerar contradição.
2- Uma fórmula H é uma contradição se a suposição ∃ I | I[H] = T gerar contradição.
3- Uma fórmula H é factível quando ela não for tautologia, nem contradição. Neste caso, basta
apresentar duas interpretações para H (I e J), onde I[H] = T e J[H] = F.
4- Duas fórmulas G e H são equivalentes semanticamente, se for possível provar que a fórmula
G ↔ H for uma tautologia.
5- Uma fórmula G implica semanticamente na fórmula H, se for possível provar que a fórmula
G → H for uma tautologia.
  • Princípio da Indução Finita
Apesar de não fazer parte da lógica, este princípio é um dos principais métodos utilizados na demonstração de resultados. Na ciência da computação, tal princípio é usado para demonstrar resultados em linguagens formais, teoria de algoritmos, teoria dos códigos, etc.
Paradigma da Indução
Considere um conjunto de peças de dominó enfileiradas e enumeradas. Elas estão dispostas de modo que, se o dominó 1 é derrubado para direita, então o subseqüente (dominó 2) também cai, e assim sucessivamente.
Diante disto, surge a pergunta: “O que é suficiente para um dominó N cair?”
Resposta: que qualquer um dos dominós que o antecede caia para direita, ou seja, existem (N-1) condições suficientes.
Suponhamos que o dominó 1 caia para direita, logo o dominó N também cai. Agora surge outra pergunta: “Qual é a condição necessária para que o dominó 1 possa cair para direita?”.
Resposta: que os dominós subseqüentes possam ser derrubados.
A partir deste cenário, observamos que existem várias condições suficientes para que todos os dominós sejam derrubados. Exemplo:
Se o dominó 1 é derrubado para direita, então o dominó N cai, ou simplesmente, D1 → DN.
Dentre eles, destacamos 2 conjuntos:
1º conjunto:
     • Condição básica: O dominó 1 é derrubado para direita.
     • Condição indutiva: Seja N um nº arbitrário. Se o dominó N é derrubado para direita, então o dominó N+1 também cai.
2º conjunto:
     • Condição básica: O dominó 1 é derrubado para direita.
     • Condição indutiva: Seja N um nº arbitrário. Se todos os dominós até N são derrubados para direita, então o dominó N+1 também cai.
Note, que ambos tem a mesma condição básica. Entretanto, a condição indutiva é ligeiramente modificada.
O princípio da indução finita possui 2 formas que correspondem a estes conjuntos. Neste curso iremos abordar apenas a 1ª forma.
  • 1a Forma de Indução
Suponha que para cada N (N ≥ 1), seja dada a asserção A(N). Para concluirmos que A(N) é verdadeira para todo inteiro N, deve ser possível demonstrar as seguintes propriedades:
• Base da Indução: A asserção A(1) é verdadeira.
• Passo Indutivo: Dado um inteiro N (N ≥ 1), se A(N) é verdadeira, então A(N+1) também é verdadeira.
Exercício: Demonstre, através do princípio da indução finita, que: dada a progressão geométrica ai+1 = ai+q, para q ≠ 1. A soma dos N primeiros termos desta progressão pode ser calculada por:
Captura de Tela 2014-09-23 às 04.18.36
Formas Normais
 
As fórmulas da lógica proposicional podem ser expressas utilizando vários conjuntos de conectivos completos. Além disso, também podemos representá-las através de estruturas pré-definidas, denominadas formas normais. São elas:
• Forma Normal Disjuntiva (FND): se a fórmula é uma disjunção de conjunções de literais
(símbolos proposicionais ou suas negações).
• Forma Normal Conjuntiva (FNC): se a fórmula é uma conjunção de disjunções de literais.
Ex: H = (¬P ∧ Q) ∨ (¬R ∧ ¬Q ∧ P) ∨ (P ∧ S) FND
 G = (¬P ∨ Q) ∧ (¬R ∨ ¬Q ∨ P) ∧ (P ∨ S) FNC
Obtenção das Formas Normais
 
Considere a fórmula: H = (P → Q) ∧ R. Podemos escrever H1 e H2, de modo que H1 seja H na FND e H2 seja H na FNC, com segue:
P Q R H
F F F F
F F T T
F T F F
F T T T
T F F F
t F T F
T T F F
T T T T

2º Passo: Geração de H1 (FND).

– Extrair as linhas da tabela-verdade onde I[H] = T. Para cada linha N, gerar uma fórmula YN, formada apenas pela conjunção de literais, de modo que I[YN] = T, como apresentado abaixo:
2ª linha: I[P] = F, I[Q] = F, I[R] = T ⇒ Y2 = (¬P ∧ ¬Q ∧ R).
4ª linha: I[P] = F, I[Q] = T, I[R] = T ⇒ Y2 = (¬P ∧ Q ∧ R).
8ª linha: I[P] = T, I[Q] = T, I[R] = T ⇒ Y2 = (P ∧ Q ∧ R).
– Gerar H1 a partir da disjunção das fórmulas geradas no item anterior.
H1 = (¬P ∧ ¬Q ∧ R) ∨ (¬P ∧ Q ∧ R) ∨ (P ∧ Q ∧ R) 
3º Passo: Geração de H2 (FNC).
– Extrair as linhas da tabela-verdade onde I[H] = F. Para cada linha N, gerar uma fórmula XN, formada apenas pela disjunção de literais, de modo que I[XN] = T, como apresentado abaixo:
1ª linha: I[P] = F, I[Q] = F, I[R] = F ⇒ X1 = (P ∨ Q ∨ R).
3ª linha: I[P] = F, I[Q] = T, I[R] = F ⇒ X3 = (P ∨ ¬Q ∨ R).
5ª linha: I[P] = T, I[Q] = F, I[R] = F ⇒ X5 = (¬P ∨ Q ∨ R).
6ª linha: I[P] = T, I[Q] = F, I[R] = T ⇒ X6 = (¬P ∨ Q ∨ ¬R).
7ª linha: I[P] = T, I[Q] = T, I[R] = F ⇒ X7 = (¬P ∨ ¬Q ∨ R).
– Gerar H2 a partir da conjunção das fórmulas geradas no item anterior.
H2 = (P ∨ Q ∨ R) ∧ (P ∨ ¬Q ∨ R) ∧ (¬P ∨ Q ∨ R) ∧ (¬P ∨ Q ∨ ¬R) ∧ (¬P ∨ ¬Q ∨ R) 
 
 
Dedução de Teoremas
O processo de prova por dedução consiste em demonstrar que, dadas algumas expressões como verdadeiras (hipóteses ou premissas), uma nova sentença também é verdadeira. Quando isso ocorre, dizemos que a sentença provada é um teorema com respeito às hipóteses.
A prova de um teorema consiste em derivar a expressão desejada H a partir das hipóteses β, utilizando os recursos disponíveis em algum dos sistemas de dedução válidos (β |– H).
Definição (sistemas de dedução): também denominados sistemas formais, são completos (se β ⇒ H, então β |– H) e corretos (se β |– H, então β ⇒ H) e estabelecem estruturas que permitem a representação e dedução do conhecimento.
  • TIPOS DE SISTEMAS DE DEDUÇÃO
Os sistemas de dedução podem ser divididos em 2 grupos, como segue:
     • Sistemas de difícil implementação computacional:
          Sistema Axiomático
          Dedução Natural
     • Sistemas mais adequados para implementação computacional:
          o Tableaux Semânticos
          o Resolução
Neste curso, apresentaremos o sistema axiomático e a resolução.
Sistema Axiomático
 
O sistema axiomático é uma estrutura para representação e dedução do conhecimento baseado em axiomas. Ele é definido pela composição de 4 elementos:
     • Alfabeto da lógica proposicional;
     • Conjunto de fórmulas proposicionais (Hipóteses)
     • Subconjunto de fórmulas, denominados axiomas; e
     • Conjunto de regras de inferência.
HIPÓTESES
As hipóteses ou premissas são fórmulas proposicionais tidas (assumidas) como verdadeiras.
Assim, caso se descubra que uma das hipóteses pode ser falsa, toda prova feita a partir desta hipótese perde sua validade.
AXIOMAS
 
Os axiomas representam o conhecimento dado a priori. No caso do sistema axiomático, este conhecimento é representado por tautologias.
O conjunto de fórmulas axiomáticas pode variar entre os sistemas axiomáticos. Porém, independente do conjunto adotado, o mesmo deve assegurar o sistema axiomático seja completo e correto.
Neste curso, adotaremos um sistema cujos axiomas são determinados pelos esquemas:
• Ax1 = ¬(H ∨ H) ∨ H ⇔ (H ∨ H) → H
• Ax2 = ¬H ∨ (G ∨ H) ⇔ H → (G ∨ H)
• Ax3 = (¬(¬H ∨ G)) ∨ ((¬(E ∨ H)) ∨ (G ∨ E)) ⇔ (H → G) → ((E ∨ H) → (G ∨ E))
sendo, H, G e E quaisquer fórmulas preposicionais.
REGRAS DE INFERÊNCIA
 
As regras de inferência são implicações semânticas. Elas são utilizadas para fazer inferências, ou seja, executar os “passos” de uma demonstração ou dedução.
Assim como os axiomas, o conjunto de regras de inferência adotado em um sistema axiomático pode variar, desde que mantenham as propriedades de completude e correção. Quanto menor o conjunto de regras de inferência, mais elegante é o sistema axiomático.
Abaixo serão listadas algumas regras de inferência que podem ser utilizadas em um sistema
axiomático:
Captura de Tela 2014-09-22 às 19.10.05

Captura de Tela 2014-09-22 às 19.10.29

OBS: A maioria dos sistemas axiomáticos costuma utilizar apenas o Modus Ponens (MP) como regra de inferência.
PROVA EM UM SISTEMA AXIOMÁTICO
Uma prova ou demonstração através do sistema axiomático consiste em apresentar a seqüência de passos necessários para derivar a fórmula desejada a partir das hipóteses. Cada passo pode ser a geração de um axioma ou a aplicação de uma regra de inferência.
Proposição: dado um teorema com as hipóteses H1, H2, …, HN e a fórmula a ser provada C. Ele é verdadeiro sempre que:
Captura de Tela 2014-09-22 às 19.11.39
Exercício 1: Prove P → (S ∨ G) através de um sistema axiomático que utiliza todas as regras de
inferência apresentadas acima e com o seguinte conjunto de hipóteses:
P → (Q ∨ R)
Q → S
R → G
Solução:
– considerando as hipóteses:
P → (Q ∨ R) (1)
Q → S (2)
R → G (3)
– Aplicando o dilema construtivo entre (2) e (3), temos:
(Q ∨ R) → (S ∨ G) (4)
– Aplicando o silogismo hipotético entre (1) e (4), temos:
P → (S ∨ G) c.q.d
PROVA POR ABSURDO
Neste tipo de prova, nega-se a fórmula que se deseja provar, a inclui no conjunto de hipóteses e aplica as regras de inferência até se obter um absurdo.
Exercício: A partir das hipóteses abaixo e utilizando apenas o Modus Ponens (MP) como regra de inferência, prove P.
¬S → P
R ∨ ¬P
¬S
Solução:
– Considerando as hipóteses:
     ¬S → P (1)
     R ∨ ¬P (2)
     ¬S (3)
     ¬P (4) Negação do teorema
– Aplicando a equivalência (G → H ⇔ ¬H → ¬G) em (1), temos:
     ¬P → S (5)
– Aplicando MP entre (4) e (5), temos:
     S (6)
Como (6) contradiz (3), conclui-se que a suposição inicial (¬P) é falsa. Logo β |– P c.q.d.
DERIVAÇÃO SEM HIPÓTESES
Além das provas onde uma fórmula G é derivada a partir de um conjunto de hipóteses β (β |– G), existem casos onde o sistema axiomático não possui hipóteses (β é vazio) e a fórmula desejada é derivada somente a partir dos axiomas, denotamos: |– G.
Ex: Utilizando um sistema axiomático sem hipóteses e apenas com Modus Ponens como regra de inferência, prove (P ∨ ¬P).
– Para gerar uma sentença que contenha a fórmula a ser derivada, utilizamos o Ax3 com H = (P ∨ P), E = ¬P e G = P, temos:
     ((P ∨ P) → P) → ((¬P ∨ (P ∨ P)) → (P ∨ ¬P)) (1)
– Note que a parte antecedente de (1) pode ser gerada a partir de Ax1 para H = P:
     (P ∨ P) → P (2)
– Aplicando MP entre (2) e (1), temos:
      ((¬P ∨ (P ∨ P)) → (P ∨ ¬P)) (3)
– A parte antecedente de (3) pode ser gerada a partir de Ax2 para H = P e G = P:
     ¬P ∨ (P ∨ P) (4)
– Aplicando MP entre (4) e (3), temos:
     (P ∨ ¬P) c.q.d.
Resolução
Ao contrário do sistema axiomático, no método de resolução não se tem axiomas. Portanto, este método é definido pela composição dos seguintes elementos:
• Alfabeto da lógica proposicional;
• Conjunto de cláusulas, geradas a partir de fórmulas proposicionais (Hipóteses)
• Regra de inferência.
A resolução é um método de prova aplicado sobre fórmulas que estão na forma de conjunções de disjunções, conhecida como forma normal conjuntiva (FNC).
Ex: H = (P ∨ ¬Q ∨ R) ∧ (R ∨ Q) ∧ (¬P ∨ ¬R ∨ ¬P)
Cada fórmula é, então, representada na forma de conjunto de cláusulas (FCC). Nesta notação, cada disjunção é um subconjunto (cláusula), onde o conectivo ou é trocado por uma vírgula. Além disso, as vírgulas entre os subconjuntos representam a conjunção (conectivo e) das disjunções.
Ex: H = {{P, ¬Q, R}, {R, Q}, {¬P, ¬R}}
Note que no exemplo acima, {¬P, ¬R} representa (¬P ∨ ¬R ∨ ¬P). Isto ocorre, pois não se representa duplicidade na notação de conjuntos (FCC).
REGRA DE INFERÊNCIA
O mecanismo de inferência da resolução utiliza apenas uma regra, denominada regra de resolução, como segue:
Captura de Tela 2014-09-22 às 19.19.43
Captura de Tela 2014-09-22 às 19.19.58