CS245 Assignments 14 Summary
Assignment 4
 Bottom Introduction and Negation Elimination are
interchangeable.
 Solutions prefer
Reflexive to Reflexivity.

Contradiction Elimination or
Negation Introduction only result in producing a formula in negation of the top one. If the top
one was negated, we would resolve in
doublenegated form, but sometimes mistakes would occur when you subconsciously write down the negationfree
form as if you applied the
double negation elimination rule on that one. In this case, we could have used
PBC with a range from the top, in negated form, to the contradiction, in order to avoid the mistake.
 Be careful that you must make sure you start the main proof with
Premise rather than
Assumption.
 If we are not allowed to use any derived rule but wishing to achieve the same performance as
LEM, we could negate the conclusion and prove a contradiction. Finally, we end up using the
double negation elimination rule to reach the conclusion.
 The same mistake as above. In an implication, by
MT, if the conclusion if wrong, we may resolve in the negation of that hypothesis. If the hypothesis
was in negation, we have to resolve in double negation, rather than mistakenly negationfree form.
 Be clear about the difference between
Negation Introduction and
Contradiction Elimination. By applying Contradiction Elimination, we may invent any formula but
must lie within the same subproof. By applying Negation Introduction, however,
outside the subproof, we resolve in the negation of the top formula of that subproof.
 An interesting way to prove
 To disprove a statement ,we must exhibit an example rather than justification.
Assignment 3
Determining Dead Code
 To discuss reachability of programs in arithmetics, try to explicitly state the property, e.g. transitivity,
Circuit Design
 Establish a corresponding truth table and focus on the rows in the truth table where the output
is true.
 Convert each such row into a propositional formula, and then convert all four formulas together using
.
 Assemble them into one final formula using disjunctions.
Entailment
 To prove that an entailment holds, construct
as any truth valuation such that
.
 Try to reason that under the same
, the formula to be entailed is also
.
 To prove that an entailment does NOT hold, construct a particular
with the property that under
,
, while the formula to be entailed is
under that
.
Adequate Sets of Connectives
 To prove that a set is an adequate set of connectives for Propositional Logic, use the fact that some set is proved an adequate set, e.g. {
,
} for Propositional Logic, and represent every connective in the proved set by the set to be proved.
 To prove that a set is not an adequate set of connectives for Propositional Logic, sometimes, use Structural Induction to prove that certain property of Wellformed Propositional Formulae fail to possess, e.g. failing to have negation property,
i.e. every Wellformed Propositional Formula remains true under the set of connectives.
Structural Induction
 Sometimes, only one connective case is necessary to present, and the other ones can be omitted by mentioning that they are similar to the proof of the former one.
 By Structural Induction, we can prove that certain property that holds for atoms, also, hold for Wellformed Propositional Formulae.
Assignment 2
Structural Induction with Prefix Involved
 In binary cases, prefixes can both be a part of formulae
and
. Thus, we need to discuss them case by case:
 the prefix of
,
 the whole part of
 the whole part of
concatenated with the prefix of
 the whole part of
and
Valuation Tree
 We might be asked to present a valuation tree in alphabetical order, since a valuation tree can be established in more than one way.
 Alternatively, every question that can be done by valuation tree can be done with truth table.
Tautology, Contradiction, Satisfiable
 Every formula that is a tautology is satisfiable.

cannot be a contradiction. If
itself was a contradiction, then no matter which
we choose, that formula is a tautology and hence, we can find an
such that for all
we cannot form a contradiction.
 Read questions carefully. Do NOT ignore some part of question, e.g. providing an evaluation.
Assignment 1
Subtleties of Translating Propositions
 Conjunctions
 I will fly to Vancouver although I like taking the train.
 I am feeling very sick nonetheless I wrote my exam.
 I will go to the doctor despite not being sick.
 Although , nonetheless and despite implicitly assign conjunction to formulae.
 Only If
 I will go to work only if I am not tired.
 I go to work implies I am not tired.

In Lieu of
 I will play hockey in lieu of playing soccer.
 I will play hockey and I wonâ€™t play soccer.

Subscripted Propositions