Propositional Logic - Language

DEFINITIONS

Definition 1.1. The symbols of L_P are:
(1) Parentheses: ( and ).
(2) Connectives: : ¬ and →.
(3) Atomic formulas: A0, A1, A2, . . . , An, . . .
We still need to specify the ways in which the symbols of L_P can
be put together.

Definition 1.2. The formulas of L_P are those finite sequences or strings of the symbols given in Definition 1.1 which satisfy the following
rules:
(1) Every atomic formula is a formula.
(2) If α is a formula, then (¬α) is a formula.
(3) If α and β are formulas, then (α → β) is a formula.
(4) No other sequence of symbols is a formula.

PROBLEMS AND PROPOSITIONS

Problem 1.1. Why are the following not formulas of L_P? There
might be more than one reason. . .
(1) A₋₅₆
(2) (Y → A)
(3) (A7 ← A4)
(4) A7 → (¬A5))
(5) (A₈A₉ → A_1043998
(6) (((¬A1) → (A_l → A₇) → A₇)
Symbols not in the language, unbalanced parentheses, lack of
connectives. . .

Problem 1.2. Show that every formula of L_P has the same number
of left parentheses as it has of right parentheses.
The key idea is to exploit the recursive structure of Definition 1.2 and proceed by induction on the length of the formula or on the number of connectives in the formula. As this is an idea that will be needed repeatedly in Parts I, II, and IV, here is a skeleton of the argument in this case:
Proof. By induction on n, the number of connectives (i.e. occurrences of ¬ and/or →) in a formula φ of L_P, we will show that any formula φ must have just as many left parentheses as right parentheses.
Base step: (n = 0) If φ is a formula with no connectives, then it
must be atomic. (Why?) Since an atomic formula has no parentheses
at all, it has just as many left parentheses as right parentheses.
Induction hypothesis: (n ≤ k) Assume that any formula with n ≤ k connectives has just as many left parentheses as right parentheses.
Induction step: (n = k + 1) Suppose φ is a formula with n = k +1
connectives. It follows from Definition 1.2 that φ must be either
(1) (¬α) for some formula α with k connectives or
(2) (β → γ ) for some formulas β and γ which have ≤ k connectives each.
(Why?) We handle the two cases separately:
(1) By the induction hypothesis, φ has just as many left parentheses
as right parentheses. Since φ, i.e. (¬α), has one more
left parenthesis and one more right parentheses than α, itmust
have just as many left parentheses as right parentheses as well.
(2) By the induction hypothesis, β and γ each have the same number of left parentheses as right parentheses. Since φ, i.e.
(β → α), has one more left parenthesis and one more right
parnthesis than β and γtogether have, it must have just as
many left parntheses as right parentheses as well.
It follows by induction that every formula φ of L_P has just as many
left parentheses as right parentheses.

Problem 1.3. Suppose α is any formula of L_P. Let l(α) be the length of α as a sequence of symbols and let p(α) be the number of parentheses (counting both left and right parentheses) in α. What are the minimum and maximum values of p(α)/l(α)?
Compute p(α)/l(α) for a number of examples and look for patterns. Getting a minimum value should be pretty easy.

Problem 1.4. Suppose α is any formula of L_P. Let s(α) be the number of atomic formulas in α (counting repetitions) and let c(α) be the number of occurrences of → in α. Show that s(α) = c(α) + 1.
Proceed by induction on the length of or on the number of connectives in the formula.

Problem 1.5. What are the possible lengths of formulas of L_P ?
Prove it.
Construct examples of formulas of all the short lengths that you can, and then see how you can make longer formulas out of shortones.

Problem 1.6. Find a way for doing without parentheses or other
punctuation symbols in defining a formal language for propositional
logic.
Hewlett-Packard sells calculators that use such a trick. A similar
one is used in Defiition 5.2.

Proposition 1.7. Show that the set of formulas of L_P is countable.
Observe that L_P has countably many symbols and that every
formula is a finite sequence of symbols. The relevant facts from set
theory are given in Appendix A.

Problem 1.8. Take a couple of English sentences with several connectives
and translate them into formulas of L_P. You may use ∧, ∨, and ↔ if appropriate.
Stick several simple statements together with suitable connectives.

Problem 1.9. Write out ((α ∨ β )∧( β → α)) using only ¬ and →.
This should be straightforward.

Problem 1.10. Write out ¬(α ↔ ¬δ)^β → ¬α → γ first with the
missing parentheses included and then as an official formula of L_P .
Ditto.

Syllabus IT – INFORMATION TECHNOLOGY

ENGINEERING MATHEMATICS

Mathematical Logic:

Propositional Logic; First Order Logic.

Probability:

Conditional Probability; Mean, Median, Mode and Standard Deviation; Random Variables; Distributions; uniform, normal, exponential, Poisson, Binomial.
Set Theory & Algebra: Sets; Relations; Functions; Groups; Partial Orders; Lattice; Boolean Algebra.

Combinatorics:

Permutations; Combinations; Counting; Summation; generating functions; recurrence relations; asymptotics.

Graph Theory:

Connectivity; spanning trees; Cut vertices & edges; covering; matching; independent sets; Coloring; Planarity; Isomorphism.

Linear Algebra:

Algebra of matrices, determinants, systems of linear equations, Eigen values and Eigen vectors.

Numerical Methods:

LU decomposition for systems of linear equations; numerical solutions of non-linear algebraic equations by Secant, Bisection and Newton-Raphson Methods; Numerical integration by trapezoidal and Simpson’s rules.

Calculus:

Limit, Continuity & differentiability, Mean value Theorems, Theorems of integral calculus, evaluation of definite & improper integrals, Partial derivatives, Total derivatives, maxima & minima.

FORMAL LANGUAGES AND AUTOMATA

Regular Languages:

finite automata, regular expressions, regular grammar.

Context free languages:

push down automata, context free grammars

COMPUTER HARDWARE

Digital Logic:

Logic functions, minimization, design and synthesis of combinatorial and sequential circuits, number representation and computer arithmetic (fixed and floating point)

Computer organization:

Machine instructions and addressing modes, ALU and data path, hardwired and micro-programmed control, memory interface, I/O interface (interrupt and DMA mode), serial communication interface, instruction pipelining, cache, main and secondary storage

SOFTWARE SYSTEMS

Data structures and Algorithms:

the notion of abstract data types, stack, queue, list, set, string, tree, binary search tree, heap, graph, tree and graph traversals, connected components, spanning trees, shortest paths, hashing, sorting, searching, design techniques (greedy, dynamic,
divide and conquer, Algorithm design by induction), asymptotic analysis (best, worst, average cases) of time and space, upper and lower bounds, Basic concepts of complexity classes – P, NP, NP-hard, NP-complete.

Programming Methodology:

Scope, binding, parameter passing, recursion, C programming – data types and declarations, assignment and control flow statements, 1-d and 2-d arrays, functions, pointers, concepts of object-oriented programming - classes, objects, inheritance, polymorphism, operator overloading.
Operating Systems (in the context of Unix): classical concepts (concurrency, synchronization, deadlock), processes, threads and inter-process communication, CPU scheduling, memory management, file systems, I/O systems, protection and security, shell programming.

Information Systems and Software Engineering:

information gathering, requirement and feasibility analysis, data flow diagrams, process specifications, input/output design, process life cycle, planning and managing the project, design, coding, testing, implementation, maintenance.

Databases:

E-R diagrams, relational model, database design, integrity constraints, normal forms, query languages (SQL), file structures (sequential, indexed), b-trees, transaction and concurrency control.

Data Communication and Networks:

ISO/OSI stack, transmission media, data encoding, multiplexing, flow and error control, LAN technologies (Ethernet, token ring), network devices – switches, gateways, routers, ICMP, application layer protocols – SMTP, POP3, HTTP, DNS, FTP,
Telnet, network security – basic concepts of public key and private key cryptography, digital signature, firewalls

Web technologies:

Proxy, HTML, XML, basic concepts of cgi-bin programming.