Questions about truth tables, conjunctive and disjunctive normal forms, negation, and implication of unquantified propositions would fit very nicely under this tag. Questions about other kind of logics should be tagged with [logic] instead.

learn more… | top users | synonyms (1)

5
votes
1answer
90 views
+50

Construct an OR gate when missing input information

Is there a way to construct an OR gate when the input for one combination is unknown? For example, suppose that the gate, $X$, outputs for the following inputs, $x_1$ and $x_2$, $x_1 = T$, $x_2 = ...
0
votes
2answers
35 views

What's next step to prove this boolean expression?

I need to prove that the first member of this equivalence is true: $$(p\vee q)\wedge (\sim p \wedge (\sim p\wedge q))\equiv \sim p \wedge q$$ I have reached the following point, but I don't know how ...
2
votes
1answer
58 views

Proving $(p\to q)\lor (r\to s) \vdash (p\to s)\lor(r\to q)$ using Fitch notation

I'm supposed to prove the validity of the following $(p\to q)\lor (r\to s) \vdash (p\to s)\lor(r\to q)$ I'm very new to natural deduction, so I still haven't got a "feel" about it. I can prove ...
-1
votes
2answers
26 views

Proof using deductive system and modus ponens

The axioms, if p and q are two sentences p$\Rightarrow$(q$\Rightarrow$p) (p$\Rightarrow$(q$\Rightarrow$r))$\Rightarrow$((p$\Rightarrow$q)$\Rightarrow$(p$\Rightarrow$r)) ...
0
votes
1answer
37 views

Difference between a proposition and an assertion

It may be a silly doubt, but let me ask this. What is the difference between a proposition and an assertion? I know there's a very thin line between the two terminologies, but I'm unable to get ...
0
votes
1answer
36 views

If $\models \neg \phi$, then $\models \phi^\circ$, where $\phi^\circ$ is the “semi-dual” of $\phi$

This is exercise 1.3.22 from Hinman's Fundamentals of Mathematical Logic. Let $\mathrm{Sent}_{\neg, \vee, \wedge}$ be the set of all sentences from propositional logic closed under negation, ...
2
votes
1answer
41 views

Proof of derivability

I'm a beginner at mathematical logic and I've come across the following problem: Let $X, Y \subset \mathcal{F}$, where $\mathcal{F}$ is the set of all formulas, and assume that $X \cup \{ \lnot ...
2
votes
4answers
119 views

Proof that $B \land ( B \lor C) = B$?

In my logic design exam today I was given this question: Show that: $$ B \land ( B \lor C) = B $$ It's asking for a proof for this expression. Could someone please explain how such expression ...
1
vote
2answers
38 views

Is the replacement theorem true for conditionals?

I read about the replacement theorem in Kleene's intro to logic which is as follows: If $\vDash(A\sim B)$ then $\vDash(C_A\sim C_B)$ where $C_A$ is a formula containing formula $A$ and $C_B$ is ...
7
votes
6answers
882 views

What is a constructive proof of $\lnot\lnot(P\vee\lnot P)$?

Glivenko's theorem says that $\lnot\lnot P$ is a theorem of intuitionistic logic whenever $P$ is a theorem of classical logic. Is it closely related to the so-called Gödel–Gentzen negative translation ...
1
vote
1answer
44 views

Playing with propositional truth-tables

The following is the truth-table describing the definitions which allow us to establish truth values to composite formulae or molecules, which is nothing new: I had an idea about playing with the ...
1
vote
1answer
39 views

Let $\alpha\in \text{FORM}$. If $\beta \in Sub( \alpha) \implies \beta $ shows up in every formation chain of $\alpha$.

Warning: I'm translating from spanish so probably many terms may sound unfamiliar. Warning 2: I'm probably going to link this question from many others I ask so I don't copy and paste these ...
0
votes
3answers
48 views

Counterexample to “$A \to B, A \to C$, therefore $B \to C$”

We have $A\to B$ and $A\to C$. I need counter-examples to: '$\therefore B\to C$'. More formally, disprove: $$ (A\to B)\land(A\to C)\to (B\to C)$$ I have $A$ is a blackbird, $B$ is 'is black', $C$ ...
-1
votes
1answer
42 views

Proving unsatisfiability with propositional resolution

I'm having trouble understanding how to use the resolution rule to prove if a statement is satisfiable or unsatisfiable. I watched this course lecture on propositional resolution and unsatisfiability ...
3
votes
2answers
66 views

Is the following a correct logical proof?

A → (F ∧ P) ~A → (S ∧ R) ~R ∴ P     assume ~P         assume A         F ∧ P ...
3
votes
1answer
51 views

Proofs as implication and proving implications

I am working through a textbook, on my own, having to do with logic and mathematical proofs, and I have a question about a problem I just completed. Here's the problem: "Suppose $P \to (Q \to ...
4
votes
1answer
48 views

Why is the rule “If x has type σ in the context, we know that x has type σ” needed?

I am trying to get a deeper understanding of why the rules in logic and type theories exist, and am now looking at the simply typed lambda calculus, the typing rules on Wikipedia. The first one is ...
1
vote
1answer
466 views

proof of validity of tautology in first order logic

Every first-order logic formula which has a tautological shape in propositional logic is a valid formula. Will it be possible to give a formal proof for the above ? Thanks and Regards.
0
votes
2answers
34 views

Show that $(A\Delta B) \cup C = (A\cup C) \Delta (B\setminus C)$

Show that $(A\Delta B) \cup C = (A\cup C) \Delta (B\setminus C)$ I want to show it algebraically, but I just can't make it work.
0
votes
4answers
73 views

Equivalence of $P\rightarrow Q$ and $\lnot P\lor Q$

How do we explain the logical equivalence $$(P\rightarrow Q ) \equiv [(\neg P)\; \vee \; Q]$$ and if possible could you please give an example illustrating this equivalence. Thanks alot !!
0
votes
1answer
18 views

Propositional Logic - Conditional Proof

I'm confused doing one problem. The problem is to show that $$(P\vee Q \implies R) \implies (P\wedge Q \implies R)$$ using Rule C.P. What I have done so far: Assumed antecedent of the conclusion as ...
1
vote
1answer
62 views

Are the logical [equivalence] laws sound and adequate without de Morgan's law?

I need to say whether the system of logical laws made of: Double negation Commutative Associative Distributive Idempotent Implication Contradiction de Morgans Absorption Equivalence is sound and ...
2
votes
1answer
76 views

Questions about Gödel, formal systems, propositional calculus and first order logic.

I've been reading Hofstadter's Gödel, Escher, Bach: An Eternal Golden Braid, and I'm loving it, though there are some things I don't quite understand yet. Propositional Calculus is a formal system, ...
0
votes
1answer
31 views
-1
votes
1answer
37 views

Solve the following proof : M |- M ∨ {[(Z∨S) ∧ (¬] → (C↔D)}

Solve the following proof : M |- M ∨ {[(Z∨SC↔D)} I try to proof above question with the following (F⋀Z)⋀ → (C↔D) 1 (F⋀Z)→C 2 F⋀Z 1⋀E 3 F 2⋀E really confused :( this ...
6
votes
2answers
90 views

Law of Clavius explained

Law of Clavius states $ \sim P \Rightarrow P \vdash P$ And the only explanation I sort of understand is ...
1
vote
1answer
38 views

Universal 2-bit gates

I'd like to show that there is no set of 2 bit reversible gates which is universal. I'm not sure as to where & how do I start here? I tried to assume by contradiction that such a set exists, thus ...
1
vote
2answers
39 views

Analyzing logical form of the statements

I have four statements given as exercises in the book: How to prove it. Sa : Alice and Bob are not both in the room. Sb : Alice and Bob are both not in the room. Sc : Either Alice or Bob is not ...
2
votes
3answers
4k views

Proving/Disproving Product of two irrational number is irrational

I saw this question where I had to prove/disprove that: Ques. Product of two irrational number is irrational. I tried 'Proof by Contraposition'. Product of two irrational number is irrational. p ...
1
vote
3answers
67 views

Omitting parantheses in formulas

Lately I read the following: parentheses can always be omitted, so instead of $((\neg A)\Rightarrow B)$ we may write $(\neg A)\Rightarrow B$. But we may not write $\neg A\Rightarrow B$, because ...
1
vote
2answers
31 views

Solving Boolean expression

(A+C+D)(A+C+D’)(A+C’+D)(A+B’) This is my first attempt on solving four algebraic terms using boolean expression. I am stuck,please help me. I have a test tommorow. Thanks!
2
votes
2answers
28 views

is bitwise xor completely distributive?

The bitwise xor operator has the following truth table: $$ \begin{array}{c|cc} \text{^}&0&1\\ \hline 0&0&1\\ 1&1&0 \end{array} $$ It is true that if $a,b,c,d$ are boolean ...
4
votes
1answer
77 views

Why do we need truth functional completeness?

This might sound a little too basic, perhaps too basic for most people to talk about. The question seems vaguely structured - I'm not sure how to phrase it better. Question: Why do we need truth ...
0
votes
5answers
86 views

Is it necessary for a statement to have an inverse in propositional logic?

I know that it may be rather self-evident that every statement must possess an inverse, however, is there a way to prove this in propositional calculus or is it considered an axiom? (Note: By the ...
5
votes
1answer
204 views

Formal proof of $(A\lor B)∨C \leftrightarrow A\lor(B\lor C)$

$A\lor B$ by definition $\neg A\implies B$ Deduction rules: $A\implies (B\implies A)$ $(A\implies (B\implies C))\implies ((A\implies B)\implies(A\implies C))$ $(\neg B\implies \neg ...
7
votes
8answers
668 views

Conditional Statements: “only if”

For some reason, be it some bad habit or something else, I can not understand why the statement "p only if q" would translate into p implies q. For instance, I have the statement "Samir will attend ...
2
votes
1answer
111 views

$A⇒(B \lor C)$ and $[(A \Rightarrow B) \lor (A \Rightarrow C)]$

[(A⇒ B∨C)] ⇒ [A⇒(¬B⇒C)] ⇒[(A⇒¬B)⇒(A⇒C)] ⇒ [¬(A⇒¬B)∨(A⇒C)]⇒[(A∧B)∨(A⇒C)] [(A⇒B)∨(A⇒C)] is equivalent to A⇒(B∨C). Can I prove [(A∧B)∨(A⇒C)] ⇒ [A⇒(B V C)]? or is there problem in the proof above ...
8
votes
2answers
64 views

How many truth tables if there are only $\land$ or $\lor$ for $n$ variables?

For example, if we have three operators $\land, \lor$ and $\neg$. For $n$ variables, there will be $2^{2^n}$ different truth tables. Because for $2^n$ rows of the truth table, there are $2$ choices - ...
1
vote
3answers
82 views

How to prove a logical implication?

Question: Using the Laws of Logic and Rules of Inference, prove that $$(\neg(\neg p \lor q) \lor r) \Rightarrow (\neg p \lor (\neg q \lor r)).$$ I just don't know how to apply the Rules of ...
4
votes
10answers
6k views

How do I prove this statement is tautology without using truth tables?

How do I prove the following statement is a tautology, without using truth tables? $$[¬P ∧ (P ∨ Q)] → Q$$ I know that if we assume $Q ≡ T$ then no matter what the truth value of what is to the left ...
2
votes
0answers
24 views

Can an equation be shown to be valid through logic over an continuous range?

I may be asking the impossible - but would appreciate it if someone else were to confirm this for me, rather than me just thinking this... I have a black box function, $f(x)$ that I don't know ...
2
votes
1answer
30 views

How does one go from this step: $(\neg p \lor \neg q) \lor (p \lor q)$ to this one: $(\neg p \lor p) \lor (\neg q \lor q)$

I'm reviewing discrete math a second time (after it being over a decade since I took the course in college). How does one go from this step: $(\neg p \lor \neg q) \lor (p \lor q)$ to this one: $(\neg ...
0
votes
2answers
70 views

Valid Formula in First Order Logic

I am a little confused about the validity of first order logic formulas. How we can using formal notation to prove the following is VALID? $ \exists x \exists ...
0
votes
1answer
42 views

First Order Logic Question

$\forall x\ \forall y\ P(x,y) \to \forall x\ \forall y\ P(y,x)$ Is this a tautology? Is there a set method that we can use to find whether a wff is a tautology?
0
votes
2answers
107 views

Solving Logical equivalence & propositional logic problems without truth tables

I have no particular "Logic question" in hand at the time being, but need help to understand a way that can be used to prove "Logical equivalence without using truth tables". moreover can we solve ...
0
votes
2answers
43 views

Solve it by using logical proposition

Show that given logical proposition is tautology $((A \implies C) \land (B \implies C) \land \lnot C) \implies \lnot (A \lor B) $ I can apply the implication rule first and got $\lnot((A \implies ...
8
votes
6answers
2k views

Help to understand material implication

This question comes from from my algebra paper: $(p \rightarrow q)$ is logically equivalent to ... (then four options are given). The module states that the correct option is $(\sim p \lor q)$. ...
1
vote
1answer
56 views

How Do You Show That There Exist Infinitely Many Organic Tautologies?

This question takes inspiration from this question. A tautology is organic if none of it's proper sub-formulas are tautologies. In other words, if all of the sub-formulas excluding the formula ...
0
votes
1answer
42 views

Proof of formulas in sequent calculus

Is there an algorithm for proof of formulas in sequent calculus, like resolution method? I'm especially interested in natural deduction. UPDATE Well, we have one scheme of axioms $$\Phi\vdash\Phi$$ ...
2
votes
3answers
3k views

What is Validity and Satisfiability in a propositional statement?

I tend to see these words a lot in Discrete Mathematics. I assumed these were just simple words until I bumped into a question. Is the following proposition Satisfiable? Is it Valid? $(P ...