Logic 1: Basics Flashcards
List some examples of the important applications of logic in computer science…
- Formal specifications;
- Verifying code is correct instead of testing;
- Programming languages (e.g. Prolog);
- Databases (e.g. SQL).
Formal methods covers areas such as:
- mathematical specification of software
- specification of network protocols
- proof of correctness of implementations
- derivation of software from specifications
Most logics are extensions
or variations of the two classical logics. Name them…
Propositional logic and predicate logic (also called
first-order logic).
What is an atomic proposition?
A basic statement.
How can we build compound propositions?
By using atomic propositions.
What is a proposition formed by connecting two propositions with the word ‘and’ called?
A conjunction.
What is a proposition formed by connecting two propositions with the word ‘or’ called?
A disjunction.
In Propositional logic, do we interpret ‘or’ in (1) the inclusive sense: (meaning either. . . or . . . or both’), or in (2) the exclusive sense: (meaning ‘either . . . or . . . but not both’).
We always use ‘or’ in the inclusive sense (meaning either. . . or . . . or both’).
Besides (and) conjunction and (or) disjunction, we shall use two other logical connectives which
build a new proposition from two old ones. What are they?
Implication (‘if . . . then’), and bi-implication (if and only if’).
What is the order of precedence? (highest 1st)
Negation, conjunction, disjunction,
implication, bi-implication.
When using an implicaiton (if…then), is cause and effect relevant?
We must always assume the implication is being used in the
weaker sense; that is, with no attendant notion of cause and effect.
How is ‘not A’ abbreviated in propositional logic?
¬A
How is ‘A and B’ abbreviated in propositional logic?
A ∧ B
How is ‘A or B’ abbreviated in propositional logic?
A ∨ B
How is ‘If A then B’ abbreviated in propositional logic?
A → B
How is ‘A if and only if B’ abbreviated in propositional logic?
A ↔ B
How would the sentence ‘If he is honest, then I am the Pope’ be represented using abbreviated connectives?
‘He is honest → I am the Pope’.
Besides
the propositional variables, it is convenient to include two special atomic propositions, referred to as constant propositions. What are they?
True and false.
What are the two constant propositions?
True and false.
What are true and false referred to in Propositional logic?
Constant propositions.
When we translate an English sentence into a propositional logic formula (p → q), which part is the logical connective(s), and which is the propositional variable(s)?
the logical
connective is (→) and the propositional variables are (p, q).
Translate the following english sentance into a propositional logic formula: ‘If you find a buyer for your house, then pigs will fly’.
p → q
Why do we use propositional variables?
In order to state general properties of propositional variables efficiently, as we are not concerned with the
internal structure of the atomic propositions.
What are the following rules that a string of propositional variables and connectives must conform to in order to be a valid propositional formula?
- A propositional variable is a formula
- true and false are formulae
- If A is a formula, then so is (¬A)
- If A and B are formulae, then so are (A ∧ B), (A ∨ B), (A → B) and (A ↔ B)
