introduction to logic

Question 1

Why do we need a special language, why not just english:

Answer 1

English is so rich that it cannot be formally described

The meaning of an English sentence can be ambiguous – sentences such as this sentence is false cannot have a truth value as it is a semantic paradox

Question 2

what are the two fundamental aspects of logic?

Answer 2

a system of deduction by which proofs can be constructed ie a proof system

a notion of meaning by which the truth (or falsity) of some property of some object can be determined ie its semantics

Question 3

why do we use symbol?

Answer 3

We use symbols because language is so rich that it limits the power of language to create issues

Question 4

what are the three components of logic?

Answer 4

Syntax – the definition of the well formed formulae of logic

Semantics – the association of meaning and truth to the formulae of the logic

Proof systems – the manipulation of formulae according to a system of rules

Question 5

who was regarded as the founder of logic?

Answer 5

Aristotle was the founder – he resonded in syllogism – for example socrates is a man , all men are mortal, therefore socrates is mortal

Question 6

what would we like from the semantics, syntax and a proof system?

Answer 6

all the “true” (semantics) formulae should be “provable” (syntax, proof system) ie completeness

a formula that is “provable” (syntax, proof system) should be “true” (semantics) ie soundness.

Question 7

what can temporal logic do?

Answer 7

Temporal logic can be used to reason over time steps `

Question 8

What does a syntax of a programming language determine?

Answer 8

it determines exactly which combinations of symbols constitute a legitimate program.

Question 9

how can we give a semantics to our programs?

Answer 9

initially, all variables have some given non-negative integer values

we execute the program, with the usual definitions of + and –.

Question 10

how can you define a given program p?

Answer 10

an input for a given program is a specification v of a non-negative integer value for every variable of p

Question 11

When would an input v satisy p?

Answer 11

An input v might be said to satisfy p if throughout the execution of p with the variables initially valued by v , no variable ever takes a negative value.

Question 12

What is a database?

Answer 12

A structured collection of logical records

Question 13

What is a database query language?

Answer 13

A language for asking and answering questions of this structured data

Question 14

Where are almost all database query languages built on?

Answer 14

SQL

Question 15

What is the expressive power of SQL closely related to?

Answer 15

Predicatae logic

Question 16

What are formal methods?

Answer 16

Use of mathematically based techniques for the specification and verification of computer systems. Prove that programs have certain properties don’t just rely on testing

Question 17

What is model checking?

Answer 17

It is a branch of formal methods

The computer system is first modelled as some mathematical structure then a specific property that this system might have is expressed by a formula of some logic

Question 18

how are formal methods used in microprocessor designs?

Answer 18

Microprocessor design – all major microprocessor manufacturers use model checking methods as a part of their desing procress

Question 19

how are formal methods used in design of data communication protocol software?

Answer 19

Design of data communication protocol software- model checkers have been used as rapid prototyping systems for validating new data communications/ security protocols

Question 20

how are formal methods used in critical software?

Answer 20

Critical software – NASA used model checking to look for bugs in code developed by the space program

Question 21

how are formal methods used in operating systems?

Answer 21

Operating systems – microsoft uses model checking to verify the correct functioning of new windows device drivers

Question 22

what did Frege attempt to do?

Answer 22

He attempted to show that all mathematics grew out of logic

Question 23

what was Frege intentions to show and what would that mean?

Answer 23

His intention was to show that there was a set of axioms (basic and obvious facts) and a set of logical rules (unambiguous) so that all true mathematical statements expressible in Frege’s logic could be inferred from these axioms and using these rules.

Question 24

What is russles paradox?

Answer 24

In Frege’s logical system, one could define certain sets of objects, Russell showed that the set R can be so defined R = {A is a set : where A is not in the set of A}. The paradox arises when one asks whether R is not in the set of R, if R is not in the set of R then R satisfies the premise to be in R so R is in the set of R. if R is is in the set of R then R satisfies the premise to be in R so R is not in the set of R.

Question 25

How can you fobid russels paradox

Answer 25

you have to forbid the set for which A Is a set and A is not in the set of A

Question 26

What is Godels incompleteness theorem?

Answer 26

in any acceptable logical system powerful enough to describe the arithmetic of the natural numbers, there are true things about the natural numbers that cannot be proven in the system

Question 27

what did hilbert believe?

Answer 27

all mathematical statements could be written in a formal language and manipulated according to formal rules
all true mathematical statements could be proved in the formalism
there would be an “algorithm” to decide whetherany mathematical statement is true or not

Question 28

who destroyed hilberts programme?

Answer 28

Kurt Godel

Question 29

what is the entscheidungsproblem?

Answer 29

the Entscheidungsproblem which asks for:
- an “algorithm” that will take as input: a description of a formal language and a mathematical statement in the language
- produce as output* either “true” or “false”, according to whether the statement is true or false.

Question 30

how did turing prove the general solution to the Entscheidungsproblem is impossible?

Answer 30

Turing proved his result by reformulating Kurt Gödel’s proofs but in the context of computation and using what are now known as Turing machines.

Question 31

how did Church prove the general solution to the Entscheidungsproblem is impossible?

Answer 31

Church’s notion of a computer was the lambda calculus which led to functional programming languages such as Haskell and LISP.