Logic

Question 1

What does logic deal with?

Answer 1

Whether statements are true or false + chains of reasoning which enable us to decide this. Work with boolean + truth tables + de Morgan’s laws.

Question 2

What are the symbols for and, or not?

Answer 2

and = ^. Or = v. Not = ¬.

Question 3

What is the opposite of A^B?

Answer 3

¬A v ¬B. We find opposite by negating variable + swapping and/or symbols.

Question 4

When is A ⇒ B false?

Answer 4

When A is true and B is false.

Question 5

What is the contrapositive of A ⇒ B?

Answer 5

¬B ⇒ ¬A. They mean the same thing.

Question 6

If you chain logical deductions together, how do you know when it’s always true?

Answer 6

If the truth table is true in every scenario.

Question 7

What is forward chaining?

Answer 7

Search from initial conditions to goal. Start with what we know. Could end up with lots of intermediate deductions that aren’t needed for final answer.

Question 8

What is backward chaining?

Answer 8

From goal back to initial conditions. Start with what we want to know. Can end up with lots of questions which we don’t need an answer to.

Question 9

What is propositional logic?

Answer 9

Logic used when something must be proved/disproved (proposition)

Question 10

What is predicate logic?

Answer 10

When we need to find out more about unknown variable before we can prove/disprove it. It tells you something about the subject and so is a Boolean function applied to 1 or more variables.

Question 11

What happens when you add values to a predicate?

Answer 11

It becomes a proposition.

Question 12

What is the domain/universe of discourse?

Answer 12

Set of values which can be assigned to predicate variable.

Question 13

What are the quantifiers?

Answer 13

For all (∀) or there exists (∃) to indicate num of values for which predicate is true. For all shows all values are true. There exists shows at least one (possibly all) values are true for predicate. E.g. ∀x∈D .P(x) (for all possible values of x in domain D, P(x) is true.

Question 14

What is a counterexample?

Answer 14

With for all, there must be at least 1case where p(x) is false so ¬( ∀x∈D.P(x)) = ∃x∈D.¬P(x) AND ¬( ∃x∈D .P(x) ) = ∀x∈D.¬P(x). You flip rule + negate predicate. Domain not affected.

Question 15

How do you prove ‘there exists’?

Answer 15

You just need 1 example.

Question 16

What is the lovers relationship?

Answer 16

Use 2 different quantifiers. Let L(a,b) be ‘a loves b’. Can use statements such as ∀x∈D. ∃y∈D.L(y,x) meaning everyone is loved by someone

Question 17

What is the difference between a finite and infinite sequence?

Answer 17

Finite sequences we know length and can specify each term’s index, we limit domain to num of terms in sequence. Strong parallel between ∀i + for loops for arrays. With infinite, we don’t know how many there are but if there’s a pattern we can make a conjecture about subsequent terms so can make a predicate rule for this.

Question 18

What is the difference between an ordered and a sorted sequence?

Answer 18

A sequence is already ordered but sorted means in asc/desc order.

Question 19

What is the Fibonacci sequence?

Answer 19

Addition of previous 2 numbers in sequence but have to declare first 2 values as don’t have 2 previous values.

Question 20

How do we concatenate sequences?

Answer 20

Tie symbol means concatenation, join 2 sequences together (⌢).

Question 21

How do we declare a subsequence in predicate logic?

Answer 21

Use subseq(S,T) to state if something is a subsequence, but not in VDMLab. To ref subsequence, use S(starti,…,endi)

Question 22

How can we use predicate logic for sequences of word?

Answer 22

Create predicate that detects repeated words e.g. ∃i∈{2,…,len(S)}.S(i)=S(i-1). If word spelt wrong, check if every word is in dictionary. E.g. ∀I ∈{1,…,len(S)}. ∃J ∈{1,…,len(D)}.S(i)=D(j).