$((A\cap B)\oplus A{)}^{\prime}={A}^{\prime}\cup B$

A′ is A complement.

Noelanijd
2022-07-15
Answered

Can someone help me prove that:

$((A\cap B)\oplus A{)}^{\prime}={A}^{\prime}\cup B$

A′ is A complement.

$((A\cap B)\oplus A{)}^{\prime}={A}^{\prime}\cup B$

A′ is A complement.

You can still ask an expert for help

berouweek

Answered 2022-07-16
Author has **11** answers

Step 1

$\begin{array}{}\text{aka Xor}& p\oplus q\equiv (p\wedge \mathrm{\neg}q)\vee (\mathrm{\neg}p\wedge q)\equiv (p\vee q)\wedge (\mathrm{\neg}p\vee \mathrm{\neg}q)\end{array}$

This set notation '$\oplus $' corresponding to xor in logic.

Any $x\in ((A\cap B)\oplus A{)}^{\prime}$ if and only if:

$\mathrm{\neg}((x\in A\wedge x\in B)\oplus x\in A)$

Since $\mathrm{\neg}((p\wedge q)\oplus p)\leftrightarrow (\mathrm{\neg}p\vee q)$ is a tautology,

It's clearly equivalent to $x\notin A\vee x\in B$, hence proved…

Apply def. of Xor:

$\mathrm{\neg}(((x\in A\wedge x\in B)\wedge x\notin A)\vee (\mathrm{\neg}(x\in A\wedge x\in B)\wedge x\in A))$

Apply Commutative law & Associative law:

$\mathrm{\neg}(((x\in A\wedge x\notin A)\wedge x\in B)\vee (\mathrm{\neg}(x\in A\wedge x\in B)\wedge x\in A))$

Apply Negation law:

$\mathrm{\neg}((\mathrm{\perp}\wedge x\in B)\vee (\mathrm{\neg}(x\in A\wedge x\in B)\wedge x\in A))$

Apply Domination law:

$\mathrm{\neg}(\mathrm{\perp}\vee (\mathrm{\neg}(x\in A\wedge x\in B)\wedge x\in A))$

Apply Identity law:

$\mathrm{\neg}(\mathrm{\neg}(x\in A\wedge x\in B)\wedge x\in A)$

Apply De Morgan's law:

$\mathrm{\neg}((x\notin A\vee x\notin B)\wedge x\in A)$

Apply Distributive law:

$\mathrm{\neg}((x\notin A\wedge x\in A)\vee (x\notin B\wedge x\in A))$

Apply Negation law:

$\mathrm{\neg}(\mathrm{\perp}\vee (x\notin B\wedge x\in A))$

Apply Domination law:

$\mathrm{\neg}(x\notin B\wedge x\in A)$

Apply De Morgan's law:

$x\in B\vee x\notin A$

Apply Commutative law:

$x\notin A\vee x\in B$

This hold if and only if $x\in {A}^{\prime}\cup B$

Step 2

Hence we proved $\begin{array}{}\u25fb& ((A\cap B)\oplus A{)}^{\prime}={A}^{\prime}\cup B\end{array}$

$\begin{array}{}\text{aka Xor}& p\oplus q\equiv (p\wedge \mathrm{\neg}q)\vee (\mathrm{\neg}p\wedge q)\equiv (p\vee q)\wedge (\mathrm{\neg}p\vee \mathrm{\neg}q)\end{array}$

This set notation '$\oplus $' corresponding to xor in logic.

Any $x\in ((A\cap B)\oplus A{)}^{\prime}$ if and only if:

$\mathrm{\neg}((x\in A\wedge x\in B)\oplus x\in A)$

Since $\mathrm{\neg}((p\wedge q)\oplus p)\leftrightarrow (\mathrm{\neg}p\vee q)$ is a tautology,

It's clearly equivalent to $x\notin A\vee x\in B$, hence proved…

Apply def. of Xor:

$\mathrm{\neg}(((x\in A\wedge x\in B)\wedge x\notin A)\vee (\mathrm{\neg}(x\in A\wedge x\in B)\wedge x\in A))$

Apply Commutative law & Associative law:

$\mathrm{\neg}(((x\in A\wedge x\notin A)\wedge x\in B)\vee (\mathrm{\neg}(x\in A\wedge x\in B)\wedge x\in A))$

Apply Negation law:

$\mathrm{\neg}((\mathrm{\perp}\wedge x\in B)\vee (\mathrm{\neg}(x\in A\wedge x\in B)\wedge x\in A))$

Apply Domination law:

$\mathrm{\neg}(\mathrm{\perp}\vee (\mathrm{\neg}(x\in A\wedge x\in B)\wedge x\in A))$

Apply Identity law:

$\mathrm{\neg}(\mathrm{\neg}(x\in A\wedge x\in B)\wedge x\in A)$

Apply De Morgan's law:

$\mathrm{\neg}((x\notin A\vee x\notin B)\wedge x\in A)$

Apply Distributive law:

$\mathrm{\neg}((x\notin A\wedge x\in A)\vee (x\notin B\wedge x\in A))$

Apply Negation law:

$\mathrm{\neg}(\mathrm{\perp}\vee (x\notin B\wedge x\in A))$

Apply Domination law:

$\mathrm{\neg}(x\notin B\wedge x\in A)$

Apply De Morgan's law:

$x\in B\vee x\notin A$

Apply Commutative law:

$x\notin A\vee x\in B$

This hold if and only if $x\in {A}^{\prime}\cup B$

Step 2

Hence we proved $\begin{array}{}\u25fb& ((A\cap B)\oplus A{)}^{\prime}={A}^{\prime}\cup B\end{array}$

iarc6io

Answered 2022-07-17
Author has **2** answers

Step 1

Note that $\oplus $ denotes the symmetric difference between two sets. In other words,

$P\oplus Q=(P-Q)\cup (Q-P)=(P\cap {Q}^{\prime})\cup (Q\cap {P}^{\prime})$

Step 2

Using this definition as well as set identities, we have the following proof:

$(}(A\cap B)\oplus A{{\textstyle )}}^{\prime$

$={\textstyle [}{\textstyle (}(A\cap B)\cap {A}^{\prime}{\textstyle )}\cup {\textstyle (}A\cap (A\cap B{)}^{\prime}{\textstyle )}{{\textstyle ]}}^{\prime}$ ----- by definition of $\oplus $

$={\textstyle [}{\textstyle (}(B\cap A)\cap {A}^{\prime}{\textstyle )}\cup {\textstyle (}A\cap (A\cap B{)}^{\prime}{\textstyle )}{{\textstyle ]}}^{\prime}$ ----- by the commutative law

$={\textstyle [}{\textstyle (}B\cap (A\cap {A}^{\prime}){\textstyle )}\cup {\textstyle (}A\cap (A\cap B{)}^{\prime}{\textstyle )}{{\textstyle ]}}^{\prime}$ ----- by the associative law

$={\textstyle [}(B\cap \mathrm{\varnothing})\cup {\textstyle (}A\cap (A\cap B{)}^{\prime}{\textstyle )}{{\textstyle ]}}^{\prime}$ ----- by the complement law

$={\textstyle [}\mathrm{\varnothing}\cup {\textstyle (}A\cap (A\cap B{)}^{\prime}{\textstyle )}{{\textstyle ]}}^{\prime}$ ----- by the domination law

$={\textstyle [}A\cap (A\cap B{)}^{\prime}{{\textstyle ]}}^{\prime}$ ----- by the identity law

$={A}^{\prime}\cup (A\cap B{)}^{\u2033}$ ----- by DeMorgan's law

$={A}^{\prime}\cup (A\cap B)$ ----- by the double complement law

$=({A}^{\prime}\cup A)\cap ({A}^{\prime}\cup B)$ ----- by the distributive law

$=U\cap ({A}^{\prime}\cup B)$ ----- by the complement law

$={A}^{\prime}\cup B$ ----- by the identity law

Note that $\oplus $ denotes the symmetric difference between two sets. In other words,

$P\oplus Q=(P-Q)\cup (Q-P)=(P\cap {Q}^{\prime})\cup (Q\cap {P}^{\prime})$

Step 2

Using this definition as well as set identities, we have the following proof:

$(}(A\cap B)\oplus A{{\textstyle )}}^{\prime$

$={\textstyle [}{\textstyle (}(A\cap B)\cap {A}^{\prime}{\textstyle )}\cup {\textstyle (}A\cap (A\cap B{)}^{\prime}{\textstyle )}{{\textstyle ]}}^{\prime}$ ----- by definition of $\oplus $

$={\textstyle [}{\textstyle (}(B\cap A)\cap {A}^{\prime}{\textstyle )}\cup {\textstyle (}A\cap (A\cap B{)}^{\prime}{\textstyle )}{{\textstyle ]}}^{\prime}$ ----- by the commutative law

$={\textstyle [}{\textstyle (}B\cap (A\cap {A}^{\prime}){\textstyle )}\cup {\textstyle (}A\cap (A\cap B{)}^{\prime}{\textstyle )}{{\textstyle ]}}^{\prime}$ ----- by the associative law

$={\textstyle [}(B\cap \mathrm{\varnothing})\cup {\textstyle (}A\cap (A\cap B{)}^{\prime}{\textstyle )}{{\textstyle ]}}^{\prime}$ ----- by the complement law

$={\textstyle [}\mathrm{\varnothing}\cup {\textstyle (}A\cap (A\cap B{)}^{\prime}{\textstyle )}{{\textstyle ]}}^{\prime}$ ----- by the domination law

$={\textstyle [}A\cap (A\cap B{)}^{\prime}{{\textstyle ]}}^{\prime}$ ----- by the identity law

$={A}^{\prime}\cup (A\cap B{)}^{\u2033}$ ----- by DeMorgan's law

$={A}^{\prime}\cup (A\cap B)$ ----- by the double complement law

$=({A}^{\prime}\cup A)\cap ({A}^{\prime}\cup B)$ ----- by the distributive law

$=U\cap ({A}^{\prime}\cup B)$ ----- by the complement law

$={A}^{\prime}\cup B$ ----- by the identity law

asked 2021-07-28

Let A, B, and C be sets. Show that

asked 2021-08-02

Suppose that A is the set of sophomores at your school and B is the set of students taking discrete mathematics at your school. Express each of these sets in terms of A and B.

a) the set of sophomores taking discrete mathematics in your school

b) the set of sophomores at your school who are not taking discrete mathematics

c) the set of students at your school who either are sophomores or are taking discrete mathematics

Use these symbols: $\cap \cup$

asked 2020-11-09

Use proof by Contradiction to prove that the sum of an irrational number and a rational number is irrational.

asked 2021-08-18

Discrete Mathematics Basics

1) Find out if the relation R is transitive, symmetric, antisymmetric, or reflexive on the set of all web pages.where $(a,b)\in R$ if and only if

I)Web page a has been accessed by everyone who has also accessed Web page b.

II) Both Web page a and Web page b lack any shared links.

III) Web pages a and b both have at least one shared link.

asked 2022-07-14

asked 2021-08-18

In how many ways can a 10-question true-false exam be answered? (Assume that no questions are left blank)

asked 2022-09-05

Derive a homogenous linear recurrence from ${x}_{n}={2}^{n}+{F}_{n}$

Suppose that the sequence ${x}_{n}$ satisfies that

$${x}_{n}={2}^{n}+{F}_{n}$$

where $\{{F}_{n}\}$ denotes the Fibonacci sequence, I want to derive a homogenous linear recurrence for ${x}_{n}$

I can show that

$${x}_{n}-{x}_{n-1}-{x}_{n-2}=\frac{1}{4}{2}^{n}$$

By plug in the relationship of Fib Sequence, however the above is non-homogenous, can anyone help?

Suppose that the sequence ${x}_{n}$ satisfies that

$${x}_{n}={2}^{n}+{F}_{n}$$

where $\{{F}_{n}\}$ denotes the Fibonacci sequence, I want to derive a homogenous linear recurrence for ${x}_{n}$

I can show that

$${x}_{n}-{x}_{n-1}-{x}_{n-2}=\frac{1}{4}{2}^{n}$$

By plug in the relationship of Fib Sequence, however the above is non-homogenous, can anyone help?