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.

View More On Wikipedia.org
Recent contents Top users
  1. L

    MHB What is the Tautology in the Given Logical Equivalence?

    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$...
  2. entropy1

    B Simple probability question: Suppose P(B|A)=1. Does that mean that P(A|B)=1?

    Suppose P(B|A)=1. Does that mean that P(A|B)=1?
  3. S

    Understanding the Distribution of Negation in Propositional Logic

    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...
  4. forkosh

    A Exploring Basis Vector Relationships in Incompatible Propositions

    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...
  5. J

    MHB Find Proofs for the following 5 propositional logic statements

    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)
  6. M

    MHB What is the simplified form of (p ∧ q) ↓ q using basic propositional logic?

    Please help me with this thing. I'm so frustrated I can't understand propositional logic Demonstrate this: (p ∧ q) ↓ q ≡ ¬q PLEASE.
  7. O

    Is it possible to prove (P→Q)↔[(P ∨ Q)↔Q] without using truth tables?

    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...
  8. Florence

    Question about propositional logic

    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...
  9. M

    I The truth value of ##P(x)## → ##Q(x)##

    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...
  10. M

    Propositional function problems

    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...
  11. Mr Davis 97

    I When are statements in propositional logic true or false?

    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...
  12. wololo

    Is Person A a Knight or a Knave on the Island?

    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...
  13. Mr Davis 97

    I Weird statement of conditions in propositional logic

    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...
  14. C

    MHB Prop Logic Proof Help: (pv~q)vr; ~pv(q.~p)/q>r

    i need help with a proof: (pv~q)vr ~pv(q.~p) / q>r this is some propositional logic thanks all
  15. Q

    Propositional Logic -- expressing in formal logic notataion

    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...
  16. Math Amateur

    MHB Propositional Logic - Derivations and Trees - Chiswell and Hodges, Section 3.4

    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...
  17. agent1594

    Symbolize propositions using predicate logic

    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...
  18. M

    Propositional logic question

    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...
  19. P

    Few propositional logic questions

    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...
  20. A

    Why translating language to propositional logic is tough?

    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...
  21. G

    MHB Can the premise P∨Q be ignored in a propositional logic proof?

    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)...
  22. G

    MHB Proving $(\neg P \to \neg Q) \to (Q \to P)$ in PL

    I'm trying to prove $$ : (\neg P \to \neg Q) \to (Q \to P)$$ in PL. Here's my attempt: $ \left\{1\right\} ~~~~~~~~~~ 1. ~~~~~~ \neg P \to \neg Q ~~~~~~~~~~~~~~~~~~~~~~ \text{Premise}$ $ \left\{2\right\} ~~~~~~~~~~ 2. ~~~~~~ Q ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ \text{Assumption for CP}$...
  23. P

    Propositional logic question

    Negate ## [\neg (p\wedge \neg q)]\wedge \neg r ## and relpace the resulting formula by an equivalent which does not involve ## \neg, \vee, \wedge ## attempt: ## \neg ([\neg (p\wedge \neg q)]\wedge \neg r) = \neg \neg (p \wedge \neg q) \vee \neg \neg r ## ## = (p \wedge \neg q) \vee r...
  24. U

    Derive all four propositional logic operators from nand

    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...
  25. C

    A propositional logic question

    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...
  26. M

    Set problems(Of which one includes propositional logic)

    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...
  27. Mathelogician

    MHB A question on consistency in propositional logic.

    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...
  28. B

    Propositional Logic: Edit Protected Wikipedia Entry Only as Admin

    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...
  29. T

    Problem with Propositional Logic

    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...
  30. L

    Please help construct a proof (propositional logic)

    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): –...
  31. M

    Can Contradiction Prove a Real Number Equals Zero?

    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.
  32. J

    Tell if this Argument is valid (Propositional Logic)?

    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...
  33. S

    Simple Boolean Algebra / Propositional Logic Question

    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...
  34. H

    Trouble with a proof in propositional logic

    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...
  35. R

    Propositional Logic Problem

    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...
  36. T

    Propositional Logic Homework Check: Proving B's Guilt

    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...
  37. S

    Propositional logic problem

    Homework Statement Can anyone prove the following p <=> q Is equivalent to: (p ^ q) V (¬p ^ ¬q)
  38. R

    Prove REPLACEMENT Theorem in Propositional Logic

    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...
  39. N

    Solving Propositional Logic and Quantifier Expressions

    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)]...
  40. cepheid

    Propositional Logic problem

    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...
  41. G

    Propositional Logic - There Exists dual

    Propositional Logic - "There Exists" dual Homework Statement "State and prove the \exists-dual of 6.1.8" Section 6.1.8 shows how to change \vdash (\forall x)(\forall y)A \equiv (\forall y)(\forall x)A via this method: (Line 1) (\forall x)(\forall y)A (Hypothesis) (Line 2) (\forall...
  42. F

    Propositional logic Discrete Mathematics

    [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...
  43. M

    How do I prove this propositional logic

    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...
  44. T

    Proving a propositional logic formula

    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))...
  45. G

    Propositional logic proof

    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...
Back
Top