Propositional Logic
What is the language of Propositional Logic or Propositional Calculus?
What is a propositional formula? Provide an example.
Formula Interpretations
What is a partial interpretation of a formula? Is it possible that the truth value of a formula can be determined in a partial interpretation? In the context of programming languages, where are partial interpretations used?
Please compare the logical operators in Java with the logical connectives (operators) of propositional logic. How are they similar or different? Do we have in Java logical operators for the implication (->) and the equivalence () operations?
Satisfiability, Validity, and Logical Equivalence
What do we understand by “logical equivalence”? How would you determine if two formulas are logically equivalent?
What is “operator elimination”? Show how operator elimination can be performed using logical equivalences.
Semantics
Consider the implication p -> q. The proposition q -> p is called the converse of p -> q. For example, the converse of the implication
If a programming language is object-oriented, then it has code reuse mechanisms
is
If a language has code reuse mechanisms, then it’s object oriented.
– Please produce an example of an implication and its converse.
– Are an implication and its converse logically equivalent? Why yes? Why not?
– Consider the implication p -> q. The proposition not p -> not q is called the inverse of p -> q. For example, the inverse of the implication
if a programming language is object-oriented, then it has code reuse mechanisms
is
if a programming language is not object-oriented, then it doesn’t have code reuse mechanisms
– Please produce an example of an implication and its inverse.
– Are an implication and its inverse logically equivalent? Why yes? Why not?
– The logical implication operation and its contrapositive are logically equivalent. That is, if A and B are formulas, then A -> B is logically equivalent to not B -> not A. What is the importance of this logical equivalence? Can you show an example?