introduction to logic Flashcards
Why do we need a special language, why not just english:
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
what are the two fundamental aspects of logic?
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
why do we use symbol?
We use symbols because language is so rich that it limits the power of language to create issues
what are the three components of logic?
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
who was regarded as the founder of logic?
Aristotle was the founder – he resonded in syllogism – for example socrates is a man , all men are mortal, therefore socrates is mortal
what would we like from the semantics, syntax and a proof system?
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.
what can temporal logic do?
Temporal logic can be used to reason over time steps `
What does a syntax of a programming language determine?
it determines exactly which combinations of symbols constitute a legitimate program.
how can we give a semantics to our programs?
initially, all variables have some given non-negative integer values
we execute the program, with the usual definitions of + and –.
how can you define a given program p?
an input for a given program is a specification v of a non-negative integer value for every variable of p
When would an input v satisy p?
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.
What is a database?
A structured collection of logical records
What is a database query language?
A language for asking and answering questions of this structured data
Where are almost all database query languages built on?
SQL
What is the expressive power of SQL closely related to?
Predicatae logic
What are formal methods?
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
What is model checking?
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
how are formal methods used in microprocessor designs?
Microprocessor design – all major microprocessor manufacturers use model checking methods as a part of their desing procress
how are formal methods used in design of data communication protocol software?
Design of data communication protocol software- model checkers have been used as rapid prototyping systems for validating new data communications/ security protocols
how are formal methods used in critical software?
Critical software – NASA used model checking to look for bugs in code developed by the space program
how are formal methods used in operating systems?
Operating systems – microsoft uses model checking to verify the correct functioning of new windows device drivers
what did Frege attempt to do?
He attempted to show that all mathematics grew out of logic
what was Frege intentions to show and what would that mean?
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.
What is russles paradox?
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.
How can you fobid russels paradox
you have to forbid the set for which A Is a set and A is not in the set of A
What is Godels incompleteness theorem?
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
what did hilbert believe?
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
who destroyed hilberts programme?
Kurt Godel
what is the entscheidungsproblem?
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.
how did turing prove the general solution to the Entscheidungsproblem is impossible?
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.
how did Church prove the general solution to the Entscheidungsproblem is impossible?
Church’s notion of a computer was the lambda calculus which led to functional programming languages such as Haskell and LISP.
