Propositional Logic Class Problem Set

1. Determine which of the following are statements:

1
)
The house is red.
This is a Statement
2
)
Today is a Tuesday.
This is a statement
3
)
A long long time ago, in a galaxy far far away..
This is not a statement, as it is not a sentence
4
)
Turn in the homework.
This is not a statement, as it does not make sense to apply a truth value to it
5
)
This statement is False.
This is not a statement, as it does not make sense to apply a truth value to it

2. Show that an implication and its converse are logically equivalent

Trick Question! an implication and its converse are not logically equivalent as can be seen by their truth tables
Out[]=
p
q
pq
qp
True
True
True
True
True
False
False
True
False
True
True
False
False
False
True
True

3. How many rows does a truth table of a proposition built out of n distinct atomic propositions have?

A truth table for a proposition with n distinct atomic propositions would have
n
2
rows.

4. Determine the Polish notation of the following propositions

1
)
(¬p∨q)(r∨s)
∨¬pq∨rs
2
)
((pq)r)s
  pqrs
3
)
(¬p∧¬q)⧦¬(p∨q)
⧦∧¬p¬q¬∨pq

5. Determine the traditional notation for the following propositions written in Polish notation,

1
)
∨¬pqpq
(¬p∨q)⧦(pq)
2
)
¬∨pqrs
¬((p∨q)⧦(rs))
3
)
↔∨pq¬∧¬p¬q
(p∨q)⧦¬(¬p∧¬q)

6. Find four non equivalent propositions built from one atomic proposition.

1
)
p
2
)
¬p
3
)
p∧¬p
4
)
p∨¬p
We can see they are nonequivalent by looking at their truth tables
Out[]=
p
p
¬p
p∧¬p
p∨¬p
True
True
False
False
True
False
False
True
False
True

7. How many non equivalent propositions can be built out of n atomic propositions?

n
2
2

8. Show that all propositions are equivalent to a proposition built from atomic propositions, negation, and disjunction.

To show this, it suffices to show that the conjunction, the implication, and the equivalence can be written using negation and disjunction. We claim that :
1
)
¬(¬p∨¬q ) is a suitable substitute for any instance of p∧q,
Out[]=
p
q
¬(¬p∨¬q)
p∧q
True
True
True
True
True
False
False
False
False
True
False
False
False
False
False
False
2
)
¬p∨q is a suitable substitute for any instance of pq, and
Out[]=
p
q
¬p∨q
pq
True
True
True
True
True
False
False
False
False
True
True
True
False
False
True
True
3
)
Using i) and ii) we note that ¬(¬(¬p∨q)∨¬(¬q∨p)) is a suitable substitute for (pq)∧(qp) which is a suitable substitute for p⧦q.
Out[]=
p
q
¬(¬(¬p∨q)∨¬(¬q∨p))
(pq)∧(qp)
p⧦q
True
True
True
True
True
True
False
False
False
False
False
True
False
False
False
False
False
True
True
True

9. The NOR ⊽ (neither or) connector is one that evaluates p⊽ to True only if both p and q are False.

1
)
Build a truth table for ⊽
Out[]=
p
q
p⊽q
True
True
False
True
False
False
False
True
False
False
False
True
2
)
Show that every proposition is equivalent to one built only using atomic propositions and ⊻ if we have a constant proposition that always evaluates to True.
By problem 8, it suffices to show that both the negation and disjunction are constructible from ⊻ and True
Out[]=
p
¬p
p⊻True
True
False
False
False
True
True
Out[]=
p
¬p
p∨q
(p⊽q)⊽(p⊽q)
True
True
True
True
True
False
True
True
False
True
True
True
False
False
False
False