Propositional logic Definition and 49 Threads

I'm taking a look at intuitionistic propositional logic (IPL). Basically it exclude Double Negation Elimination (DNE) from the set of axiom schemas replacing it with Ex falso quodlibet: ⊥ → p for any proposition p (including both atomic and composite propositions). In IPL, for instance, the Law...

I was reading a Bachelor thesis on Peano Arithmetic (PA). PA has the following axioms (not including the induction schema): $$\begin{align} & (A1) ~~~~ \forall x \neg (x + 1 = 0) \nonumber \\ & (A2) ~~~~ \forall xy (x + 1 =y + 1 \to x = y) \nonumber \\ & (A3) ~~~~ \forall x (x + 0 = x) \nonumber...

I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the...

I would ask for a clarification about the "link/connection" between syntactic vs semantic logical implication (entailment). As explained here logical consequence, syntactic logical implication (entitlement) ##\vdash## is about the existence of a formal proof within a formal system such that...

I'm still confused about the use of material implication (material conditional) ##\to## vs logical implication ##\implies##. From MSE the writing ##P \implies Q## makes the meta-logical assertion/statement that the logical statement ##Q## is logically implied by the logical statement ##P##...

A question about the Modus Ponens deduction rule used in theory of proof within an axiomatic system. $$[(p \to q) \land p ] \to q$$ One can easily check the above is a tautology (i.e. it evaluates always True for any truth value of propositions ##p## and ##q##). Now what is the logic argument...

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

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

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)

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

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

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

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

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

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}$...

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

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

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

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