What is Propositional logic: Definition and 45 Discussions
Propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. It deals with propositions (which can be true or false) and relations between propositions, including the construction of arguments based on them. Compound propositions are formed by connecting propositions by logical connectives. Propositions that contain no logical connectives are called atomic propositions.
Unlike first-order logic, propositional logic does not deal with non-logical objects, predicates about them, or quantifiers. However, all the machinery of propositional logic is included in first-order logic and higher-order logics. In this sense, propositional logic is the foundation of first-order logic and higher-order logic.
Hi guys
I can't figure this one out. I tried to use truth tables, but never found an equivalence , no matter which of the 5 options I tried.
It is given that $\alpha$ is logically equivalent to $\alpha \rightarrow \sim \beta $ .
Which of the following is a tautology ?
1) $\alpha$
2) $\beta$...
Given that the negation is distributed across parenthesis, P become ~p and S gets double negation ~~S. Hence my solution was " I will not buy the pants but I will buy the shirt. (or and I will buy the shirt, since but can be used in the place of and).
This is from How to prove things by...
If propositions ##p,q\in{\mathscr L}_{\mathcal H}## (i.e., the lattice of subspaces of ##\mathcal H##) are incompatible, then ##\hat p\hat q\neq\hat q\hat p##. But since it's a lattice, there exists a unique glb ##p\wedge q=q\wedge p##. How are they mathematically related?
In particular, I...
i came acroos the below while studying propositional Logic, can anyone find the proofs
1) P ⊢ P
2) P → Q, Q→R ⊢ P → R
3) P → Q, Q→R, ¬R ⊢ ¬P
4) Q→R ⊢ (PvQ) → (PvR)
5) P →Q ⊢ (P&R) → (Q&R)
Homework Statement
Need to demonstrate this proposition: (P→Q)↔[(P ∨ Q)↔Q] . My textbook use truth tables, but I'd like to do without it. It asks me if it's always truthThe Attempt at a Solution
Im unable to demonstrate the Tautology and obtain (¬Q) as solution.
I start by facing the right side...
Homework Statement
I have to prove that ##(p \equiv q) \equiv ((p ∧ q) ∨ (¬p ∧ ¬q))##
With no premisses
In order to prove this, I first need to prove that:
##(p \equiv q) \to ((p ∧ q) ∨ (¬p ∧ ¬q))##
And:
##((p ∧ q) ∨ (¬p ∧ ¬q)) \to (p \equiv q)##
I was able to find the second implication...
I'm reading Velleman's book titled "How to Prove it" and I'm very confused when I'm reading about conditional statements. I understand that there exists some issue with the conditional connective and I accept that because that's the cost of espousing a truth-functional view. I came here to ask...
1. Suppose P(x) and Q(x) are propositional functions and D is their domain.
Let A = {x ∈ D: P(x) is true}, B = {x ∈ D: Q(x) is true}
(a) Give an example for a domain D and functions P(x) and Q(x) such that A∩B = {}
(b) Give an example for a domain D and functions P(x) and Q(x) such that A ⊆ B...
I am studying propositional logic, and have studied how propositions can be combined with logical connectives and such, and truth tables can be used to analyze the resulted truth values, depending on the truth values of involved variables. However, when not talking in the theoretical, how do we...
Homework Statement
A person can either be a knight (always tells the truth) or a knave (always tells a lie).
On an island with three persons (A, B and C), A tells "If I am a knight, then at least one of us is a knave".
Homework Equations
Truth tables, logic rules.
The Attempt at a Solution...
So I am studying conditionals in proposition logic, and I have discovered that there are a variety of ways to phrase a conditional "if p, then q" in English. Some of the harder ones are...
p is sufficient for q
a necessary condition for p is q
q unless ~p (where ~ is the not operator)
p only...
Homework Statement
Problem from a discrete structures online open course. I don't have the answers and was quite confused about this unit, so I was hoping to check my work/ clarify a few questions.
Problem 5.5. Express each of the following predicates and propositions in formal logic notation...
I am reading the book Mathematical Logic by Ian Chiswell and Wilfred Hodges ... and am currently focused on Chapter 3: Propositional Logic and, in particular, Section 3.4: Propositional Natural Deduction ...
I need help with understanding an aspect of Example 3.4.3 which reads as...
Homework Statement
Suppose that predicates and individuals are dened as follows:
S: should be shunned,
U: is prone to unruly behaviour,
P: is a friend of Peter's,
M: is a friend of mine,
a: Ann,
d: David.
Symbolize the following:
i. Ann is a friend of Peter's and David is a friend of mine...
Homework Statement
For each of the premise-conclusion pairs below, give a valid step-by-step argument ( proof ) along with the name of the inference rule used in each step
premise { ¬ p → r ∧ ¬ s , t → s , u → ¬p , ¬w , u ∨ w } conclusion : ¬t ∨ w
Homework Equations
All...
Homework Statement
Are these propositions, if so are they true or no?
a. \sqrt{n} = 2
b. Consider an integer n: \sqrt{n} = 2 and n = 4
c. Consider an integer n: if \sqrt{n} = 2 then n = 4
Here is another question.
Translate the following into a propositional expression involving...
Why is it so hard to convert natural language to propositional logic. We are so comfortable in understanding and interpreting english or any other language we know.
But when we need to convert it into something formal, we have to think. It does not come that naturally. Why?
(I am not sure if...
I've to derive the following proposition in PL using the system in http://mathhelpboards.com/discrete-mathematics-set-theory-logic-15/propositional-logic-8386.html (in which Evgeny.Makarov has explained everything ever so kindly to me).
I'm trying to prove $\displaystyle P \vee Q, ~(R ~ \& ~ P)...
So I recently learned that you can derive all four of the propositional logic operators (~, V, &, →) from Nand alone.
As I have understood it, so long as you have negation, and one of the other operators, you can derive the rest. Like P → Q can be defined as ~P V Q.
However, I learned that...
Actually, I have several questions:
1) Why are axiom schemas the way they are? What do they represent? I know that infinitely many axioms can be written using the axiom schema form. However, what's the formal definition of axioms in predicate calculus? I've heard that the formal definition of...
I have a few questions regarding 2 set problems.
Exercise 1:
Homework Statement
1. the set A = P(empty) (the powerset of the empty set);
2. the set B = P(A);
3. the set C = P(B).
2. The attempt at a solution
1. A= {empty}
2. B = {empty, {empty}}
3. C = {empty, {empty}, {{empty}}, {empty...
Hi everybody!
We have a theorem in natural deduction as follows:
Let H be a set of hypotheses:
====================================
H U {~phi) is inconsistent => H implies (phi).
====================================
Now the question arises:
Let H={p0} for an atom p0. So H U{~p0}={p0 , ~p0}.
We...
Homework Statement
You cannot edit a protected Wikipedia entry unless you
are an administrator. Express your answer in terms of e:
“You can edit a protected Wikipedia entry” and a:“You
are an administrator."
I thought the answer would be a\rightarrow\neg e; but the actual answer is...
Hi,
I've been set an assignment, part of which is to come up with a formal proof for (p \wedge q) \Rightarrow p. I have to show that the formula is either a tautology or contradiction, or contingent. If it is contingent, I have to show the smallest possible equivalent expression that uses only...
This is a two part question my book gives as practice problem. I, however am struggling to construct logical proofs and the book does not have a key. Thanks in Advance!
2a. Construct a proof, using any method (or rules) you want, that the following argument is valid:
Premises (3): –...
Propositional logic urgent help please
Homework Statement
for every a in ℝ+:
for every ε>0 : a<ε
Homework Equations
prove that a=0
The Attempt at a Solution
is it possible to use contradiction to solve that problem, if not how can I. Urgently need help.
Tell if this Argument is valid (Propositional Logic)?
P = If a man is bachelor he is unhappy
Q= if a man is unhappy he dies young
C = so the conclusion will be Bachelors die young
is his right ?
This we have to write this in this form is this correct ----> means implies
Q ---> Q
Q...
Homework Statement
Produce the given truth table (given below as well as in a neater version in the attached Excel document) using the Boolean operators AND, OR, and/or NOT:
A (Input 1) B (Input 2) O (Output)
1 1 0
1 0 0
0 1 1
0...
Greetings everyone,
I have been teaching myself mathematical logic for amusement by going through Stephen Cole Kleene’s textbook, “Mathematical Logic”. I am stuck on the following problem (problem 13.2 on page 58, if you happen to have the book):
Show that, if |- Am+1, then A1, … , Am |- B...
1. Problem
Directions: Using propositional logic, prove that each argument is valid. Use the statement letters shown.
If the birds are flying south and the leaves are turning, then it must be fall. Fall brings cold weather. The leaves are turning but the weather is not cold. Therefore the...
Homework Statement
Either A or B (names changed) stole the exam answers. Formalize these and check if this is a correct deduction:
1) If A didn't meet B for lunch, then B is guilty or A lives in the countryside
2) If B isn't guilty, then A didn't meet B for lunch and the incident happened...
The book which i read for improving my logic sense~
There is a theorem called REPLACEMENT ..
( P \rightarrow Q ) \vee \neg ( P \rightarrow Q)
where (P\rightarrow Q) is the second occurence of ( P \rightarrow Q)
But what if the replace the second occurrence with \neg P\vee Q!
And i try...
Not sure where to post this subject, so if it is in the wrong location please forgive.
1. Restore the parentheses to these abbreviated propositional forms?
Q \wedge \backsim S \vee \backsim ( \backsim P \wedge Q )
I got this, but am not sure if it is correct.
[Q \wedge (\backsim S)]...
Homework Statement
Richard is either a knight or a knave. Knights always tell the truth, and only the truth; knaves always tell falsehoods, and only falsehoods. Someone asks, "Are you a knight?" He replies, "If I am a knight, then I'll eat my hat."
a) Must Richard eat his hat?
b) Set this up...
[SOLVED] Propositional logic Discrete Mathematics
Homework Statement
Assuming atleast one of the following statements is true, which one is it? why?
a. Exactly one of these statements is true
b. Exactly two of these statements are true
c. Exactly three of these statements are true
d...
How do I prove this? (propositional logic)
Homework Statement
How to prove this
(p \rightarrow (q \vee p)) \rightarrow r \vdash \neg p \vee (q \vee r)
using only the natural deduction rules in propositional logic?
Homework Equations
http://en.wikipedia.org/wiki/Propositional_logic...
Hello all,
first I hope there's no problem putting this question here, since I didn't find any special forum dedicated to propositional logic.
I really have very basic question, I'm trying to prove
\vdash (A \rightarrow (B \rightarrow C)) \rightarrow (B \rightarrow (A \rightarrow C))...
I want to prove (A \supset B) \wedge (B \supset C) \wedge (D \supset \neg C) \wedge (A \vee D) \equiv (B \vee \neg C)
so I have to show that \neg ( ((A \supset B) \wedge (B \supset C) \wedge (D \supset \neg C) \wedge (A \vee D)) \supset (B \vee \neg C))
is inconsistent, and I proceed as...