close

Вход

Забыли?

вход по аккаунту

код для вставкиСкачать
questions about
Propositional Logic
Exercise 1
1. Express each formula using only (at most) the
a.
b.
c.
d.
e.
connectives listed. In each case use a truth
table to prove the equivalence. (Note:  is
exclusive `or`)
Formula: pq. Connectives: {,}.
Formula: pq. Connectives: {,,}.
Formula: pq. Connectives: {, }.
Formula: (pq)  ((p)q). Conn: {,}.
Formula: p. Conn: { | } (the Sheffer stroke)
Ex. 2. Which of these are
tautologies?
1.
2.
3.
4.
5.
p (q  p)
p (p  p)
(q  p)  (p  q)
(q  p)  (p  q)
(p  (q  r))  (q  (p  r))
Please prove your claims, using truth tables.
(Hint: Ask what assignment of truth values to
p,q, and r would falsify each formula. In this
way you can disregard parts of the truth table).
Ex. 3a. Reading formulas off
truth tables
• Background: In class, a proof was
sketched for the claim that every
propositional logic formula can be
expressed using the connectives
{, }. The proof proceeded essentially by
“reading off” the correct formula off the
truth table of any given formula.
• Task: Use this meticulous method to
construct a formula equivalent to pq.
Ex. 3b. Reading formulas off
truth tables
• As Ex. 3a, but
• Task: Use the same method to construct a
formula equivalent to p|q.
• Question: Does this meticulous method
always produce the shortest answer (i.e.
the shortest formula that is logically
equivalent to the original while still only
using negation and conjunction)?
1/--страниц
Пожаловаться на содержимое документа