Questions tagged [propositional-calculus]

Appropriate for questions about truth tables, conjunctive and disjunctive normal forms, negation, and implication of unquantified propositions. Also for general questions about the propositional calculus itself, including its semantics and proof theory. Questions about other kinds of logic should use a different tag, such as (logic), (predicate-logic), or (first-order-logic).

Filter by
Sorted by
Tagged with
1
vote
1answer
58 views

Is it safe to use $|f(x)|<g(x)\iff -g(x)<f(x)<g(x)$?

Some peoples often use the following. $$|f(x)|<g(x)\iff -g(x)<f(x)<g(x)$$ The weird part occurs when $g(x)<0$, for example: $$10<f(x)<-10\to |f(x)|<-10$$ where $x\in\{\}$ for ...
-1
votes
1answer
42 views

Checking tautology

Given a Boolean formula $\phi$ in CNF form, I'll check whether there exists a clause that can be falsified i.e. check for literals of the form $x \vee \neg x$. If there are not any such literals in a ...
0
votes
1answer
27 views

Deriving intersection of two truth sets

$ \newcommand{\Set}[2]{% \{\, #1 \mid #2 \, \}% }$ Let $A = \Set{x}{P(x)}$, $B = \Set{x}{Q(x)}$. We know by definition that $$ A \setminus B = \Set{x}{P(x) \land \lnot Q(x)}.$$ Since $X \cap Y = X \...
3
votes
1answer
77 views

Can someone give me a hint on showing $(\lnot p \; \land \; (p \; \to \; q)) \; \to \; \lnot q \equiv p \; \lor \; \lnot q$?

I have to show that two compound statements are equivalent without using truth tables. I.e. $$(\lnot p \; \land \; (p \; \to \; q)) \; \to \; \lnot q \ \equiv \ p \; \lor \; \lnot q$$ I first start ...
1
vote
1answer
33 views

Propositional logic simplification using laws

I've been given the propisition below and the task to simplify it to the simplest equal proposition. $$ (p \rightarrow (q \vee r)) \rightarrow (p \wedge (q \vee r)) $$ I've been trying to do this for ...
1
vote
1answer
35 views

How to prove that a proposition that contains only $\iff$ is a tautology iff it has an even number of members $p$ [duplicate]

A proposition $φ$ consists of only $\iff$ as links. Show that $φ$ is always true iff every member $p$ (each $p$ takes either 0 or 1 as values) has an even number of showings in $φ$ At first i thought ...
1
vote
1answer
35 views

Clarification regarding an implication propositional logic question

Here is the question I am attempting to express in propositional logic: No man is weak, unless their name is bob. From this expression I see that every man who is ...
1
vote
1answer
60 views

How does this formula $A\lor (A\to B)$ relate to intuitionistic logic?

It is my first approach to the proof theory of intuitionistic logic and I am considering a single-conclusioned Gentzen-style sequent calculus for it, namely $\bf G3i$ (Negri, Von Plato, Structural ...
1
vote
1answer
61 views

English to propositional logic translation

I'm taking a discrete maths course and we're covering propositional logic. In class, we were tasked with converting the following English sentence into propositional logic: You can take a picture of ...
-1
votes
1answer
62 views

Prove that $\alpha\vee \beta$, $\alpha\to \beta$ implies $\beta$. [closed]

Prove that $\alpha\vee \beta$, $\alpha\to \beta$ implies $\beta$. Is it valid to say that this is true? And under what rule of logic can that be seen? Like Modus ponens, etc ...
2
votes
1answer
99 views

Prove the soundness of propositional logic without using induction?

I want to prove the soundness of propositional logic without using induction. I think I can do that via a process that's basically universal introduction (i.e., demonstrate something about an ...
0
votes
1answer
38 views

Modus ponens and modus tollens with embedded conditionals

What is the most concise/straightforward way to formulate modus ponens and modus tollens arguments when embedded conditionals are involved? Is the formulation below correct (for modus ponens)? (A) ⊃ B ...
0
votes
0answers
35 views

Binary subtraction using an algorithm to determine what XOR and XNOR coefficient gates to use.

Let $n \ge 0$ and $(a_i)_{\,0 \le i \le n}$, $(b_i)_{\,0 \le i \le n}$ be given where, for all $i$, $a_i, b_i \in \{0,1\}$. Let $\quad \displaystyle {a = \sum_{0 \le i \le n} a_i 2^i}$ and $\quad \...
1
vote
0answers
32 views

why is 'P implies Q' true when P is false and Q is true? [duplicate]

This is the truth table for P implies Q. i get it, When P is True and Q is True then the truth value of this "implication" function is True.('implies' function is performed correctly, if a ...
6
votes
6answers
389 views

Is there a logical system capturing these subtleties about implication?

I am teaching an introduction to proof course. The truth table for implication is always extremely difficult for students to understand. It feels, to me, that the truth table is an imperfect ...
0
votes
0answers
71 views

Can B be uniquely determined from A and A->B? Similarly, can A be uniquely determined from B and A->B?

Can $B$ be uniquely determined from $A$ and $A\rightarrow B$? Here's my attempt using the truth table: $A$ $A\rightarrow B$ $B$ T T T T F F F T T/F F F undefined (leads to a contradiction) ...
1
vote
2answers
77 views

false introduction sequent calculus?

I'm proving the following proposition using sequent calculus. I got stuck at the very top line. My thought is that if the both hypothesis inside the curly bracket are true, then it's false. So I think ...
2
votes
1answer
45 views

Rules of inference for exclusive disjunction and logical biconditional

Here are the rules of inference in natural calculus of propositions. I'd like to extend this calculus (conservatively) adding exclusive disjunction $\oplus$ and logical biconditional $\sim$ and obtain ...
0
votes
1answer
16 views

How do I Finish Simplifying this Laws of Propositional Logic Problem?

In my Discrete Mathematics class I have just started learning about the laws of propositional logic. I've got about halfway through a problem but am now stuck for a while now and I don't understand ...
2
votes
1answer
57 views

When first encountering a set of primitive inference rules, how do we approach the derivation of the very first derivable inference rules?

I'm currently learning Ebbinghaus et. al.'s propositional calculus in their book Mathematical Logic, and I'm trying to derive the very basic rules of inference such as $\land$ introduction, the law of ...
1
vote
1answer
41 views

Proving Sequent Calculus Statement

I have to prove the sequent $$\vdash (\lnot A \lor \lnot B) \to \lnot (A \land B)$$ using the inference rules for natural deduction listed here (pp. 7-8). I'm super new to natural deduction and ...
5
votes
2answers
109 views

Is this a correct derivation of Peirce's law?

I've used the rules of Chapter 2 of van Dalen's Logic and Structure, which allows only $\{ \wedge I, \wedge E, \to I, \to E, \bot E, RAA.\}$ $$ \newcommand{\bfrac}[2]{\displaystyle\genfrac{}{}{0pt}{}{#...
0
votes
2answers
41 views

Indefinite Consequent First Order Logic

Suppose I want to make the statement: For every index $i$ in the ordered Array $A$, $A[i]\leq A[i+1]$ Using first order logic I'd write it like: $\forall i($inRange$(i) \implies A[i]\leq A[i+1]) $ ...
2
votes
2answers
27 views

Let $E$ contain only the atoms $P_1,…,P_n$, and $E^*$ come from $E$ by substituting $A_1,…,A_n$ for $P_1,…,P_n$. If $E$ is valid, so is $E^*$.

Theorem 1. (Substitution for atoms.) Let $E$ be a formula containing only the atoms $P_{1},…,P_{n}$, and let $E^{*}$ come from $E$ by substituting formulas $A_{1},…,A_{n}$ simultaneously for $P_{1},…,...
1
vote
1answer
33 views

How to write the converse, contrapositive and negation of "Every planar graph can be colored with at most four colors"

I cant find a way to rewrite the statement into a conditional statement, which would make writing the converse and contrapositive easier. I was thinking about writing it as "If every planar graph ...
2
votes
1answer
92 views

How to prove $ ( p \land q ) \land \big( ( q \land \neg r ) \lor ( p \land r ) \big) $ is logically equivalent to $ \neg ( p \to \neg q ) $.\

Construct a chain of logical connectives to show that (p ∧ q) ∧ [(q ∧ ¬r) ∨ (p ∧ r)] is logically equivalent to ¬(p → ¬q). Do not use truth tables here and give a reason for each line. I could not get ...
0
votes
0answers
15 views

Algorithmic Conversion of a Propisitional Proof to a "3-coloring" of a graph.

https://www.youtube.com/watch?v=5ovdoxnfFVc&t=1273s as mentioned in the video above at 17:42, Every (propisitional) mathmatical statement can be converted to a graph (that satisfies a 3 coloring ...
1
vote
1answer
65 views

Determining the validity of conclusions based on two assumptions (WFF'N PROOF )

The Logic Problem, taken from WFF’N PROOF, The Game of Logic, has these two assumptions: “Logic is difficult or not many students like logic.” “If mathematics is easy, then logic is not difficult.” ...
1
vote
2answers
42 views

Logical inferences

Could someone please explain if Inference 2 is valid or not? I thought it would be logically valid to conclude anything based on the principle of explosion, but I'm not sure if I'm right. I'm sure ...
1
vote
2answers
65 views

Valid form and true premises makes an argument sound, but do 'premises' mean P, Q, R,... or 'what comprises the antecedent'?

Suppose we have an argument 'Disjunctive Syllogism' as below: $$P\lor Q \\{\sim}P \\∴Q.$$ which essentially means $$\big((P\lor Q)\; \&\; {\sim} P\big) \to Q.$$ Its truth table: row P Q P$\lor$Q ~...
0
votes
0answers
85 views

Provide a few examples of Boolean algebra where carrier is a finite set of finite sequences (ordered set)

I study Boolean Algebra and it is clear when: (carrier is a power set, union, intersection), (set of all divisors of n, lcm, gcd), (the set of propositional functions of n given variables, conjunction,...
1
vote
3answers
105 views

what is difference between Falsity and Falsifiability, I am thoroughly confused.

say all people in this room have worn a black suit, it could be checked if all people have actually worn a black suit and we can say it is true or not. If it is true, it is true and falsifiable, but ...
0
votes
0answers
17 views

duality between Boolean algebras and classical propositional logic as well as the algebraic structure of random events

in the book "Handbook of the History of Logic" I've read the statement that "a Boolean algebra can be interpreted both as the propositional algebra of a classical propositional logic ...
2
votes
1answer
73 views

Prove $(\Box(p\supset q)\land\Diamond(p\land r))\supset\Diamond(q\land r)$ in K

$(\Box(p\supset q)\land\Diamond(p\land r))\supset\Diamond(q\land r)$ Here's what I have so far: $((p\supset q)\land(p\land r))\supset(q\land r)$, PC-valid WFF $\Box(((p\supset q)\land(p\land r))\...
1
vote
3answers
67 views

Proving NOR is logically complete confusion

In this question I am very confused in part iii: Consider the connective ↓ (called the Pierce arrow or NOR), and defined by the truth-table below: ...
6
votes
1answer
83 views

prove or disprove: every non satisfiable set of WFF has a non satisfiable sub set such every proper subset of it is satisfiable

Let $\Gamma$ be a non-satisfiable set of well-formed formulas (wff). prove or disprove: $\Gamma$ has a non-satisfiable subset $\Delta\subseteq\Gamma$ such that for every $\phi\subsetneq\Delta$ is ...
1
vote
0answers
28 views

Proving that a set is functionally complete

Now I have been researching this for the last couple of hours trying to understand this, looking at similar questions asked on Stack but I am still very confused. This question was asked by another ...
2
votes
0answers
32 views

Is the boolean constant True a Horn formula?

The wikipedia definition of Horn formulas state that they are a conjunction of Horn clauses. So, by that logic, would it not be true that the empty conjunction, equal to the boolean constant True, is ...
4
votes
2answers
68 views

Given $\phi\sqsubset\psi$, find $\sigma$ such that $\phi\sqsubset\sigma\sqsubset\psi$.

I'm working through Van Dalen's Logic and Structure (fifth edition, 2013) independently, and have gotten stuck on problem 2.3.14(i), on p.28. The author defines: $\phi\sqsubset\psi$ if and only if $\...
-3
votes
2answers
31 views

Well formed formulas splittable over or condition

Suppose G is a set of well-formed formulas, and A and B are two well-formed formulas, I need to determine If G ⊢A or B then G ⊢A or G ⊢B This statement is true or false My Thoughts: As per my ...
1
vote
3answers
151 views

"Justification" words in symbolic logic

I am struggling with the symbolic logic equivalent of "justifications" (e.g. therefore, because, since etc.). For example: Case 1 ...
0
votes
1answer
77 views

To prove $p⊕q$, does it suffice to prove $p\implies \sim q$ and $\sim p\implies q$?

By p⊕q, also written p xor q, I mean either $p$ or $q$ but not both; and I use the symbol $\sim $ to negate propositions.
0
votes
2answers
230 views

Help in understanding a logic puzzle

Discrete Mathematics and Its Applications, 8e, by Rosen solves the following logic puzzle: As a reward for saving his daughter from pirates, the King has given you the opportunity to win a treasure ...
0
votes
6answers
182 views

Understanding the p implies q statement

The p implies q statement is often described in various ways including: (1) if p then q (i.e. whenever p is true, q is true) (2) ...
2
votes
1answer
55 views

Does the class of all topologies work as a semantics for IPC?

In this answer to this question I asked recently, the answerer said that the tautologies in the Sierpiński space are a proper superset of the intuitionistic tautologies. I'm wondering what I get when ...
1
vote
1answer
82 views

Understanding the proof of Definition by Recursion

I’m currently reading Logic and Structure by Dirk van Dalen and I am having struggles proving Theorem $2.1.6$ (Definition by Recursion) on page $10$. Warning Before someone flags this question as a ...
-1
votes
1answer
24 views

Subjective statements as propositions [closed]

I believe that subjective statements, even if declarative in nature, are never propositions. For example "Charles Barkley is an all-time great basketball player" is not a proposition because ...
0
votes
1answer
45 views

Is there an easier way to check if this proposition is a tautology?(other than truth tables) [closed]

How do I show that ((p→q)∨(r→s))→((p∨r)→(q∨s)) is a tautology? I came across this problem, spent quite some time on it and it seems there isn't a way to check if this proposition is a tautology or not....
2
votes
1answer
46 views

Undo a weakened statement in sequent calculus later in the inferences

I'm working on an answer to (b) of Mathematical Logic, Ebbinghaus et. al. 1984 p. 64 Consider the following inference: $$ \frac{\begin{align}\Gamma \vdash A\\ \Gamma \vdash B\end{align}}{\Gamma \vdash ...
2
votes
4answers
146 views

Translating "therefore" in propositional logic and using contradictions to prove an argument.

So I have the statements: A Football player is either running at the oval or sitting in the library. If he is running, then he is not reading a book. The player is reading a book. Therefore, he is ...

1
2 3 4 5
97